POJ3264 (Segment Tree, C++)

poj3264.2.cpp

#include <cstdio>

using namespace std;

#ifndef maxn
	#define maxn 50010
#endif

struct Segment {
	int left,right,value;
};

inline int lc(int p) {
	return p<<1;
}

inline int rc(int p) {
	return (p<<1)+1;
}

class SegmentTree {
	private:
		virtual int cmp(int p, int q) {
			return p<q?p:q;
		}
		Segment tree[maxn<<2];
		void build(int p, int l, int r) {
			tree[p].left=l;
			tree[p].right=r;
			if (l==r) {
				tree[p].value=data[l];
				return;
			}
			int m=(l+r)>>1;
			build(lc(p),l,m);
			build(rc(p),m+1,r);
			tree[p].value=cmp(tree[lc(p)].value,tree[rc(p)].value);
		}
		int query(int p, int l, int r) {
            if (l==tree[p].left && r==tree[p].right) return tree[p].value;
            int m=(tree[p].left+tree[p].right)>>1;
            if (r<=m) return query(lc(p),l,r); else
                if (l>m) return query(rc(p),l,r); else
                    return cmp(query(lc(p),l,m),query(rc(p),m+1,r));
        }
	public:
		int data[maxn],n;
		inline void init(void) {
			build(1,1,n);
		}
		inline int getans(int l, int r) {
			return query(1,l,r);
		}
};

class minSegmentTree: public SegmentTree {
} minTree;

class maxSegmentTree: public SegmentTree {
	private:
		int cmp(int p, int q) {
			return p>q?p:q;
		}
} maxTree;

int main() {
	int n,q;
	scanf("%d%d",&n,&q);
	minTree.n=maxTree.n=n;
	for (int i=1; i<=n; i++) {
		scanf("%d",&(minTree.data[i]));
		maxTree.data[i]=minTree.data[i];
	}
	minTree.init();
	maxTree.init();
	int l,r;
	while (q--) {
		scanf("%d%d",&l,&r);
		printf("%d\n",maxTree.getans(l,r)-minTree.getans(l,r));
	}
	return 0;
}