题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4553
线段树功能：update:区间替换 query:询问满足条件的最左断点
分析：poj3667的加强版，这里需要在每个区间内设置女神区间和屌丝区间，每次询问女神的时候，先看屌丝区间有无空位，有就插到屌丝区间内，同时更新女神区间，否则插到女神区间内，但同时也要更新屌丝区间，因为只有女神可以占用屌丝的时间，屌丝不能占用女神的时间，每次更新屌丝区间的时候直接更新即可，清空的话就是对屌丝和女神的区间都清空。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define M 1000000000 #define maxn 55555 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; int lsum[maxn<<2],rsum[maxn<<2],sum[maxn<<2]; int col[maxn<<2]; void PushDown(int rt,int m) { if(col[rt]!=-1) { col[rt<<1]=col[rt<<1|1]=col[rt]; sum[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=col[rt]?0:m-(m>>1); sum[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=col[rt]?0:m>>1; col[rt]=-1; } } void PushUp(int rt,int m) { lsum[rt]=lsum[rt<<1]; rsum[rt]=rsum[rt<<1|1]; if(lsum[rt]==m-(m>>1))lsum[rt]+=lsum[rt<<1|1]; if(rsum[rt]==m>>1)rsum[rt]+=rsum[rt<<1]; sum[rt]=max((lsum[rt<<1|1]+rsum[rt<<1]),max(sum[rt<<1],sum[rt<<1|1])); } void build(int l,int r,int rt) { col[rt]=-1; sum[rt]=lsum[rt]=rsum[rt]=r-l+1; if(l==r)return; int m=(r+l)>>1; build(lson); build(rson); } void update(int L,int R,int c,int l,int r,int rt) { if(L<=l&&r<=R) { sum[rt]=lsum[rt]=rsum[rt]=c?0:r-l+1; col[rt]=c; return; } PushDown(rt,r-l+1); int m=(r+l)>>1; if(L<=m)update(L,R,c,lson); if(R>m)update(L,R,c,rson); PushUp(rt,r-l+1); } int query(int w,int l,int r,int rt) { if(l==r)return l; PushDown(rt,r-l+1); int m=(r+l)>>1; if(sum[rt<<1]>=w)return query(w,lson); else if(rsum[rt<<1]+lsum[rt<<1|1]>=w)return m-rsum[rt<<1]+1; else return query(w,rson); } int main() { int n,m; while(scanf("%d%d",&n,&m)>0) { build(1,n,1); while(m--) { int a,b,op; scanf("%d",&op); if(op==1) { scanf("%d",&a); if(sum[1]<a)puts("0"); else { int ans=query(a,1,n,1); printf("%d ",ans); update(ans,ans+a-1,1,1,n,1); } } else { scanf("%d%d",&a,&b); update(a,a+b-1,0,1,n,1); } } } }