description
查询区间最大和最小
题解
线段树
愉悦身心啊
代码
- #include<cstring>
- #include<cstdio>
- #include<algorithm>
- #define rd read()
- #define lson nd <<1
- #define rson nd << 1 | 1
- using namespace std;
- const int N = 1e5;
- const int inf = ~0U>> 1;
- int MAX[N <<2], MIN[N << 2], a[N], q, n;
- int read() {
- int X = 0, p = 1; char c = getchar();
- for(; c> '9' || c <'0'; c = getchar()) if(c == '-') p = -1;
- for(; c>= '0' && c <= '9';c = getchar()) X = X * 10 + c - '0';
- return X * p;
- }
- void print(int x) {
- if(x <0) putchar('-'), x = -x;
- if(x>= 10) print(x / 10);
- putchar(x % 10 + '0');
- }
- void update(int nd) {
- MIN[nd] = min(MIN[lson], MIN[rson]);
- MAX[nd] = max(MAX[lson], MAX[rson]);
- }
- void build(int l, int r, int nd) {
- if(l == r) {
- MIN[nd] = MAX[nd] = a[l];
- return;
- }
- int mid = (l + r)>> 1;
- build(l, mid, lson);
- build(mid + 1, r, rson);
- update(nd);
- }
- int query_max(int L, int R, int l, int r, int nd) {
- if(L <= l && r <= R) return MAX[nd];
- int mid = (l + r)>> 1, tmp = 0;
- if(L <= mid) tmp = max(tmp, query_max(L, R, l, mid, lson));
- if(mid <R) tmp = max(tmp, query_max(L, R, mid + 1, r, rson));
- return tmp;
- }
- int query_min(int L, int R, int l, int r, int nd) {
- if(L <= l && r <= R) return MIN[nd];
- int mid = (l + r)>> 1, tmp = inf;
- if(L <= mid) tmp = min(tmp, query_min(L, R, l, mid, lson));
- if(mid < R) tmp = min(tmp, query_min(L, R, mid + 1, r, rson));
- return tmp;
- }
- int main()
- {
- n = rd; q = rd;
- for(int i = 1; i <= n; ++i) a[i] = rd;
- build(1, n, 1);
- for(int i = 1; i <= q; ++i) {
- int l = rd, r = rd;
- int mx = query_max(l, r, 1, n, 1), mn = query_min(l, r, 1, n, 1);
- print(mx - mn);
- putchar('\n');
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-2737134.html