POJ3264 (C++)

poj3264.cpp

#include <cstdio>
#include <cmath>

using namespace std;

//#define DEBUG

#ifndef maxn
  #define maxn 150000
#endif

inline int lg2(double n) {
	return floor(log(n)/log(2.0));
}

class SparseTable {
	private:
		int table[maxn][32];
		
	public:
		int data[maxn],n;
		virtual int cmp(int p, int q) {
			return p<q?p:q;
		}
		void build(void) {
			int m=lg2(n);
			for (int i=1; i<=n; i++) table[i][0]=data[i];
			for (int i=1; i<=m; i++) 
				for (int j=1; j<=n; j++) 
					table[j][i]=cmp(table[j][i-1],table[(j+(1<<(i-1)))][i-1]);
		}
		int query(int p, int q) {
			int m=lg2(q-p+1);
			return cmp(table[p][m],table[q-(1<<m)+1][m]);
		}
#ifdef DEBUG
		void print() {
			for (int i=1; i<=n; i++) printf("%d",table[i][1]);
			printf("\n");
		} 
#endif
} minTable;

class maxSparseTable: public SparseTable {
	public:
		int cmp(int p, int q) {
			return p>q?p:q;
		}
} maxTable;

int main() {
	int n,q;
	scanf("%d%d",&n,&q);
	minTable.n=maxTable.n=n;
	for (int i=1; i<=n; i++) {
		scanf("%d",&(maxTable.data[i]));
		minTable.data[i]=maxTable.data[i];
	}
	minTable.build();
	maxTable.build();
	int l,r;
#ifdef DEBUG
	minTable.print();
	maxTable.print();
#endif
	while (q--) {
		scanf("%d%d",&l,&r);
		printf("%d\n",maxTable.query(l,r)-minTable.query(l,r));
	}
	return 0;
}