经典的线段树应用，记住了。下面的博客写的真的很好
http://hi.baidu.com/billdu/blog/item/318cc859fda5d08c800a1853.html
#include<iostream> using namespace std; #define N 50005 struct node { int left,right,lval,rval,cval,bj; }; node st[N*4]; int mymax(int a,int b) { return a>b?a:b; } int mythrmax(int a,int b,int c) { return mymax(mymax(a,b),c); } int len(int i) { return st[i].right-st[i].left+1; } void init(int i) { st[i].cval=st[i].lval=st[i].rval= st[i].bj?0:len(i); return ; } void build(int l,int r,int i) { st[i].left=l; st[i].right=r; st[i].bj= i==1?0:-1; st[i].lval=st[i].cval=st[i].rval=r-l+1; if(l==r) return ; int mid=(l+r)/2; build(l,mid,2*i); build(mid+1,r,2*i+1); } int query(int i,int a) { if(st[i].left==st[i].right&&a==1) return st[i].left; if(st[i].bj!=-1) { st[2*i].bj=st[2*i+1].bj=st[i].bj; init(2*i); init(2*i+1); st[i].bj=-1; } if(st[2*i].cval>=a) return query(2*i,a); else if(st[2*i].rval+st[2*i+1].lval>=a) return st[2*i].right-st[2*i].rval+1; else if(st[2*i+1].cval>=a) return query(2*i+1,a); else return 0; } void update(int l,int r,int state,int i) { if(st[i].left>=l&&st[i].right<=r) { st[i].bj=state; init(i); return ; } if(st[i].bj!=-1) { st[2*i].bj=st[2*i+1].bj=st[i].bj; init(2*i); init(2*i+1); st[i].bj=-1; } int mid=(st[i].left+st[i].right)/2; if(l<=mid) update(l,r,state,2*i); if(r>mid) update(l,r,state,2*i+1); st[i].lval=st[2*i].lval; st[i].rval=st[2*i+1].rval; st[i].cval=mythrmax(st[2*i].cval,st[2*i+1].cval, st[2*i].rval+st[2*i+1].lval); if(st[i].lval==len(2*i)) st[i].lval+=st[2*i+1].lval; if(st[i].rval==len(2*i+1)) st[i].rval+=st[2*i].rval; return ; } int main() { int n,m,x,y,chr; scanf("%d%d",&n,&m); build(1,n,1); while(m--) { scanf("%d",&chr); if(chr==1) { scanf("%d",&x); y=query(1,x); printf("%d/n",y); if(y) update(y,y+x-1,1,1); } else { scanf("%d%d",&x,&y); update(x,x+y-1,0,1); } } return 0; }
