poj2823.cpp.tar.gz_线段树

#include <iostream> #include <stdio.h> #include <memory.h> using namespace std; #define MAXN 1000000 struct party { int min; int max; }count[5*MAXN]; int Min(int a,int b) { return a>b?b:a; } int Max(int a,int b) { return a>b?a:b; } int num[MAXN+1]; int minall[MAXN+1],maxall[MAXN+1]; void built(int left,int right,int t) { if(left==right) { count[t].min=num[left]; count[t].max=num[left]; return ; } int mid=(left+right)>>1; built(left,mid,t<<1); built(mid+1,right,(t<<1)+1); count[t].min=Min(count[t<<1].min,count[(t<<1)+1].min); count[t].max=Max(count[t<<1].max,count[(t<<1)+1].max); } party query(int left,int right,int needleft,int needright,int t) { if(left==needleft&&right==needright) return count[t]; int mid=(left+right)>>1; if(needright<=mid) return query(left,mid,needleft,needright,t<<1); if(needleft>mid) return query(mid+1,right,needleft,needright,(t<<1)+1); party now,i,j; i=query(left,mid,needleft,mid,t<<1); j=query(mid+1,right,mid+1,needright,(t<<1)+1); now.min=Min(i.min,j.min); now.max=Max(i.max,j.max); return now; } int main() { int T,Q,i; while(scanf("%d%d",&T,&Q)!=EOF) { for(i=1;i<=T;i++) scanf("%d",&num[i]); built(1,T,1); for(i=1;i<=T-Q+1;i++) { party now; now=query(1,T,i,i+Q-1,1); minall[i]=now.min; maxall[i]=now.max; } for(i=1;i<=T-Q+1;i++) { printf("%d",minall[i]); if(i!=T-Q+1) printf(" "); else printf("\n"); } for(i=1;i<=T-Q+1;i++) { printf("%d",maxall[i]); if(i!=T-Q+1) printf(" "); else printf("\n"); } } return 0; }