読者です 読者をやめる 読者になる 読者になる

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;
}