Skip to content

Instantly share code, notes, and snippets.

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