题目链接：传送门
参考文章：传送门
思路：线段树区间合并问题，每次查询到满足线段树的区间最左值，然后更新线段树。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 50500; int lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2],cover[maxn<<2]; void build(int x,int l,int r) { lsum[x]=rsum[x]=msum[x]=r-l+1; if(l==r) return ; int mid=(l+r)>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } int MAX(int x,int y) { return x>y?x:y; } void pushup(int x,int k) { lsum[x]=lsum[x<<1]; rsum[x]=rsum[x<<1|1]; msum[x]=MAX(MAX(msum[x<<1],msum[x<<1|1]),lsum[x<<1|1]+rsum[x<<1]); if(lsum[x<<1]==(k-(k>>1))) lsum[x]+=lsum[x<<1|1]; if(rsum[x<<1|1]==k>>1) rsum[x]+=rsum[x<<1]; } void pushdown(int x,int k) { if(cover[x]!=-1) { cover[x<<1]=cover[x<<1|1]=cover[x]; lsum[x<<1]=rsum[x<<1]=msum[x<<1]=cover[x]?0:(k-(k>>1)); lsum[x<<1|1]=rsum[x<<1|1]=msum[x<<1|1]=cover[x]?0:(k>>1); cover[x]=-1; } } void update(int x,int l,int r,int A,int B,int Item) { if(A<=l&&r<=B) { cover[x]=Item; lsum[x]=rsum[x]=msum[x]=Item?0:r-l+1; return ; } pushdown(x,r-l+1); int mid=(l+r)>>1; if(A<=mid) update(x<<1,l,mid,A,B,Item); if(B>mid) update(x<<1|1,mid+1,r,A,B,Item); pushup(x,r-l+1); } int query(int x,int l,int r,int len) { if(l==r) return 1; pushdown(x,r-l+1); int mid=(l+r)>>1; if(msum[x<<1]>=len) return query(x<<1,l,mid,len); else if(rsum[x<<1]+lsum[x<<1|1]>=len) return mid-rsum[x<<1]+1; else return query(x<<1|1,mid+1,r,len); } int main(void) { int n,m,i,x,y,z; while(~scanf("%d%d",&n,&m)) { build(1,1,n); while(m--) { scanf("%d",&x); if(x==1) { scanf("%d",&y); if(msum[1]<y) { printf("0 "); continue; } z=query(1,1,n,y); printf("%d ",z); update(1,1,n,z,z+y-1,1); } else { scanf("%d%d",&y,&z); update(1,1,n,y,y+z-1,0); } } } return 0; }
http://poj.org/problem?id=3667