原题：POJ-2823
一个线段树求区间最大最小
很基础的一个题目
#include <iostream> #include <cstdio> using namespace std; int n,k; int a[1000100]; int in[1000100],ax[1000100]; struct node { int mmax,mmin,l,r; node *lson,*rson; }; void buildtree(node *temp,int l,int r) { if(l==r) { temp->mmax=a[r]; temp->mmin=a[r]; temp->l=l; temp->r=l; temp->lson=NULL; temp->rson=NULL; return ; } int mid=(l+r)/2; temp->lson=new node; temp->rson=new node; buildtree(temp->lson,l,mid); buildtree(temp->rson,mid+1,r); temp->l=l; temp->r=r; temp->mmax=max(temp->lson->mmax,temp->rson->mmax); temp->mmin=min(temp->lson->mmin,temp->rson->mmin); return ; } void updata(node *node,int t,int value,int l,int r) { if(l==r&&t==l) { node->mmax=value; node->mmin=value; return ; } int mid=(l+r)/2; if(t<=mid) updata(node->lson,t,value,l,mid); else updata(node->rson,t,value,mid+1,r); node->mmax=max(node->lson->mmax,node->rson->mmax); node->mmin=min(node->lson->mmin,node->rson->mmin); } int main() { int i; while(~scanf("%d %d",&n,&k)) { for(i=0; i<n; i++) scanf("%d",&a[i]); node *head=new node; buildtree(head,0,k-1); in[0]=head->mmin; ax[0]=head->mmax; for(i=0; i<=n-k; i++) { updata(head,i%k,a[k+i],0,k-1); in[i+1]=head->mmin; ax[i+1]=head->mmax; } for(i=0; i<n-k; i++) printf("%d ",in[i]); printf("%d\n",in[i]); for(i=0; i<n-k; i++) printf("%d ",ax[i]); printf("%d\n",ax[i]); } return 0; }
