Created
July 19, 2013 02:33
-
-
Save tarawa/6034686 to your computer and use it in GitHub Desktop.
POJ3264 (Segment Tree, C++)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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