Skip to content

Instantly share code, notes, and snippets.

@tarawa
Created July 18, 2013 01:20
Show Gist options
  • Save tarawa/6025989 to your computer and use it in GitHub Desktop.
Save tarawa/6025989 to your computer and use it in GitHub Desktop.
POJ3264 (C++)
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment