第一次寫TIOJ上的線段樹 :3
#include<stdio.h>
#include<stdlib.h> #include<math.h> #include<string.h> #define N 100000 #define inf 2147483649 #define max(a,b) ((a)>(b)) ? (a):(b) #define min(a,b) ((a)>(b)) ? (b):(a) long long int TREE[N*4]; long long int MAXTREE[N*4]; long long int MINTREE[N*4]; int base; int n; void BuildTree() { for(int lx=1;lx<=n;lx++) { for(int prc=(base+lx)>>1;prc;prc>>=1) { MAXTREE[prc]=max(MAXTREE[prc],TREE[base+lx]); MINTREE[prc]=min(MINTREE[prc],TREE[base+lx]); } } } long long int FindSub(int a,int b) { long long int gmin=TREE[b+base]; long long int gmax=TREE[b+base]; for(a+=base-1,b+=base+1;(a^b^1);a>>=1,b>>=1) { if(~a&1) { gmin=min(gmin,MINTREE[a^1]); gmax=max(gmax,MAXTREE[a^1]); } if(b&1) { gmin=min(gmin,MINTREE[b^1]); gmax=max(gmax,MAXTREE[b^1]); } } return gmax-gmin; } int main() { int m;scanf("%d %d",&n,&m); memset(MINTREE,inf,sizeof(MINTREE)); base=pow(2,ceil(log2(n)))-1; for(int lx=1;lx<=n;lx++) { scanf("%I64d",&TREE[lx+base]); MINTREE[lx+base]=TREE[lx+base]; MAXTREE[lx+base]=TREE[lx+base]; } BuildTree(); for(int lx=0;lx<m;lx++) { int a,b;scanf("%d %d",&a,&b); printf("%d\n",FindSub(a,b)); } return 0; }
沒有留言:
張貼留言