题意:求区间最大值-最小值。
分析:
1、线段树
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define lowbit(x) (x & (-x)) const double eps = 1e-8; inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1; } typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const int MAXN = 50000 + 10; const int MAXT = 10000 + 10; using namespace std; int a[MAXN]; int minv[MAXN << 2], maxv[MAXN << 2]; int _min, _max; void build(int id, int L, int R){ if(L == R){ minv[id] = maxv[id] = a[L]; } else{ int mid = L + (R - L) / 2; build(id << 1, L, mid); build(id << 1 | 1, mid + 1, R); minv[id] = min(minv[id << 1], minv[id << 1 | 1]); maxv[id] = max(maxv[id << 1], maxv[id << 1 | 1]); } } void query(int l, int r, int id, int L, int R){ if(l <= L && R <= r){ _max = max(_max, maxv[id]); _min = min(_min, minv[id]); return; } int mid = L + (R - L) / 2; if(l <= mid){ query(l, r, id << 1, L, mid); } if(r > mid){ query(l, r, id << 1 | 1, mid + 1, R); } } int main(){ int N, Q; scanf("%d%d", &N, &Q); for(int i = 1; i <= N; ++i){ scanf("%d", &a[i]); } build(1, 1, N); while(Q--){ int A, B; scanf("%d%d", &A, &B); _min = INT_INF; _max = 0; query(A, B, 1, 1, N); printf("%d ", _max - _min); } return 0; }
2、RMQ
Sparse-Table算法,预处理时间O(nlogn),查询O(1)。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define lowbit(x) (x & (-x)) const double eps = 1e-8; inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1; } typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const int MAXN = 50000 + 10; const int MAXT = 10000 + 10; using namespace std; int a[MAXN]; int N, Q; int minv[MAXN][20]; int maxv[MAXN][20]; void RMQ_init(){ for(int i = 1; i <= N; ++i){ minv[i][0] = maxv[i][0] = a[i]; } for(int j = 1; (1 << j) <= N; ++j){ for(int i = 1; (i + (1 << j) - 1) <= N; ++i){ minv[i][j] = min(minv[i][j - 1], minv[i + (1 << (j - 1))][j - 1]); maxv[i][j] = max(maxv[i][j - 1], maxv[i + (1 << (j - 1))][j - 1]); } } } int RMQ(int L, int R){ int k = 0; while((1 << (k + 1)) <= (R - L + 1)) ++k; return max(maxv[L][k], maxv[R - (1 << k) + 1][k]) - min(minv[L][k], minv[R - (1 << k) + 1][k]); } int main(){ scanf("%d%d", &N, &Q); for(int i = 1; i <= N; ++i){ scanf("%d", &a[i]); } RMQ_init(); while(Q--){ int A, B; scanf("%d%d", &A, &B); printf("%d ", RMQ(A, B)); } return 0; }