poj3667 发表于 2018-04-12 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:poj3667 题解 线段树维护连续区间,hdu4553的削弱版,注意细节。。。因为一个小细节疯狂wa 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long long#define lson o<<1,l,mid#define rson o<<1|1,mid+1,rusing namespace std;const int N=1e6+7;int llen[N<<2],rlen[N<<2],mlen[N<<2],cr[N<<2],n,m,x,y;inline void pushup(int o,int len){ llen[o]=llen[o<<1];rlen[o]=rlen[o<<1|1]; if(llen[o]==len-(len>>1))llen[o]+=llen[o<<1|1]; if(rlen[o]==len>>1)rlen[o]+=rlen[o<<1]; mlen[o]=max(max(mlen[o<<1],mlen[o<<1|1]),rlen[o<<1]+llen[o<<1|1]);}inline void pushdown(int o,int len){ if(cr[o]==-1)return ; cr[o<<1]=cr[o<<1|1]=cr[o]; llen[o<<1]=rlen[o<<1]=mlen[o<<1]=cr[o]?(len-(len>>1)):0; llen[o<<1|1]=rlen[o<<1|1]=mlen[o<<1|1]=cr[o]?len>>1:0; cr[o]=-1;}inline void build(int o,int l,int r){ llen[o]=rlen[o]=mlen[o]=r-l+1;cr[o]=-1; if(l==r)return ; int mid=l+r>>1; build(lson); build(rson);}inline void update(int o,int l,int r,int L,int R,int x){ if(L<=l&&R>=r){ cr[o]=x; llen[o]=rlen[o]=mlen[o]=cr[o]?(r-l+1):0; return ; } pushdown(o,r-l+1); int mid=l+r>>1; if(L<=mid)update(lson,L,R,x); if(R>mid)update(rson,L,R,x); pushup(o,r-l+1);}inline int query(int o,int l,int r,int L,int R,int x){ if(L==R)return L; pushdown(o,r-l+1); int Mid=L+R>>1,mid=l+r>>1; if(mlen[o<<1]>=x)return query(lson,L,Mid,x); if(rlen[o<<1]+llen[o<<1|1]>=x)return Mid-rlen[o<<1]+1; return query(rson,Mid+1,R,x);}int main(){ //freopen("1.out","w",stdout); while(~scanf("%d%d",&n,&m)){ build(1,1,n); while(m--){ scanf("%d%d",&x,&y); if(x==1){ int b; if(mlen[1]<y)puts("0"); else {b=query(1,1,n,1,n,y);printf("%d\n",b);update(1,1,n,b,b+y-1,0);} } else {scanf("%d",&x);update(1,1,n,y,y+x-1,1);} } } return 0;}