HDU 1540 POJ 2892 线段树区间合并

#include "stdio.h" #include "string.h" struct node { int l,r,lx,rx,x; }data[200010]; int mark[50100]; int Max(int a,int b) { if (a<b) return b;else return a; } void build(int l,int r,int k) { int mid; data[k].l=l; data[k].r=r; data[k].lx=data[k].rx=data[k].x=data[k].r-data[k].l+1; if (l==r) return ; mid=(l+r)/2; build(l,mid,k*2); build(mid+1,k*2+1); } void updata(int x,int k,int op) { int mid,ll,rr; if (data[k].l==data[k].r) { data[k].lx=data[k].rx=data[k].x=op; return ; } mid=(data[k].l+data[k].r)/2; if (x<=mid) updata(x,k*2,op); else if (x>mid) updata(x,k*2+1,op); ll=data[k*2].r-data[k*2].l+1; rr=data[k*2+1].r-data[k*2+1].l+1; data[k].lx=data[k*2].lx; if (data[k*2].lx==ll) data[k].lx+=data[k*2+1].lx; data[k].rx=data[k*2+1].rx; if (data[k*2+1].rx==rr) data[k].rx+=data[k*2].rx; data[k].x=Max(Max(data[k*2].x,data[k*2+1].x),data[k*2].rx+data[k*2+1].lx); } int query(int x,int k) { int mid; if (data[k].l==data[k].r || data[k].x==0 || data[k].x==data[k].r-data[k].l+1) return data[k].x; mid=(data[k].l+data[k].r)/2; if (x<=mid) { if (data[k*2].r-x+1<=data[k*2].rx) return query(x,k*2)+query(mid+1,k*2+1); else return query(x,k*2); } else { if (x-data[k*2+1].l+1<=data[k*2+1].lx) return query(x,k*2+1)+query(mid,k*2); else return query(x,k*2+1); } } int main() { int cnt,n,m,x; char ch[10]; while(scanf("%d%d",&n,&m)!=EOF) { build(1,1); cnt=0; while (m--) { scanf("%s",ch); if (ch[0]=='D') { scanf("%d",&x); mark[cnt++]=x; updata(x,1,0); } if (ch[0]=='Q') { scanf("%d",&x); printf("%d ",query(x,1)); } if (ch[0]=='R') { cnt--; if (cnt<0) cnt=0; else updata(mark[cnt],1); } } } return 0; }