题目描述:
每天,农夫 John 的 n(1\le n\le 5\times 10^4)n(1≤n≤5×104) 头牛总是按同一序列排队。
有一天, John 决定让一些牛们玩一场飞盘比赛。他准备找一群在对列中为置连续的牛来进行比赛。但是为了避免水平悬殊,牛的身高不应该相差太大。John 准备了 q(1\le q\le 1.8\times10^5)q(1≤q≤1.8×105) 个可能的牛的选择和所有牛的身高 h_i(1\le h_i\le 10^6,1\le i\le n)hi?(1≤hi?≤106,1≤i≤n)。他想知道每一组里面最高和最低的牛的身高差。
思路:区间最大最小值裸题,但是这题是离线的,而且询问比较多,ST表最合适
代码:
#include<iostream> #include<string> #include<stack> #include<stdio.h> #include<queue> #include<string.h> #include<map> #include<unordered_map> #include<vector> #include<iomanip> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 150001; #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r inline int read() { int f = 1, num = 0; char ch = getchar(); while (0 == isdigit(ch)) { if (ch == ‘-‘)f = -1; ch = getchar(); } while (0 != isdigit(ch)) num = (num << 1) + (num << 3) + ch - ‘0‘, ch = getchar(); return num * f; } int st[maxn][17],Log2[maxn],st2[maxn][17]; int n, m; void build() { for (int i = 2; i <= n; i++) { Log2[i] = Log2[i / 2] + 1; } for (int k = 1; k <= 16; k++) { for (int i = 1; i + (1 << (k - 1)) <= n; i++) { st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]); st2[i][k] = min(st2[i][k - 1], st2[i + (1 << (k - 1))][k - 1]); } } } int RMQ(int l, int r) { int s = Log2[r - l + 1]; //cout <<s<<" "<< max(st[l][s], st[r - (1 << s) + 1][s]) << " " << min(st2[l][s], st2[r - (1 << s) + 1][s]) << endl; return max(st[l][s], st[r - (1 << s) + 1][s]) - min(st2[l][s], st2[r - (1 << s) + 1][s]); } int main() { //freopen("test.txt", "r", stdin); n = read(), m = read(); for (int i = 1; i <= n; i++) { st[i][0]=st2[i][0] = read(); } build(); for (int i = 1; i <= m; i++) { int a = read(), b = read(); printf("%d\n", RMQ(a, b)); } return 0; }
P2880 [USACO07JAN]Balanced Lineup G
原文：https://www.cnblogs.com/MYMYACMer/p/14439346.html