PKU 3264 Balanced Lineup
segtreeの練習. RMQみたいなことをして差を取るだけ
#include <cstdio> #include <climits> #include <algorithm> using namespace std; int hoge, N, Q, ans, tmp; typedef struct segtree{ static const int MAX_N = 1 << 18; int dat1[MAX_N * 2 - 1], dat2[MAX_N * 2 - 1]; int n; segtree(){} void init(int n_){ n = 1; while(n < n_) n *= 2; for(int i = 0; i < n * 2 - 1; i++){ dat1[i] = INT_MAX; dat2[i] = -INT_MAX; } } void update(int k, int a){ k += n - 1; dat1[k] = dat2[k] = a; while(k > 0){ k = (k - 1) / 2; dat1[k] = min(dat1[k * 2 + 1], dat1[k * 2 + 2]); dat2[k] = max(dat2[k * 2 + 1], dat2[k * 2 + 2]); } } int query1(int a, int b, int k, int l, int r){ if(r <= a || b <= l) return INT_MAX; if(a <= l && r <= b) return dat1[k]; else { int vl = query1(a, b, k * 2 + 1, l, (l + r) / 2); int vr = query1(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } int query2(int a, int b, int k, int l, int r){ if(r <= a || b <= l) return -INT_MAX; if(a <= l && r <= b) return dat2[k]; else { int vl = query2(a, b, k * 2 + 1, l, (l + r) / 2); int vr = query2(a, b, k * 2 + 2, (l + r) / 2, r); return max(vl, vr); } } } SEG; SEG seg; int main(){ scanf("%d %d", &N, &Q); seg.init(N); for(int i = 0; i < N; i++){ scanf("%d", &tmp); seg.update(i, tmp); } for(int i = 0; i < Q; i++){ int p, q; scanf("%d %d", &p, &q); p--; int tmp1 = seg.query1(p, q, 0, 0, seg.n); int tmp2 = seg.query2(p, q, 0, 0, seg.n); printf("%d\n", tmp2 - tmp1); } return 0; }