hdu1540 发表于 2018-04-08 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:hdu1540 题解 线段树维护连续区间,状态维护有点麻烦。。。 有个巨坑。。。多组输入。。。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#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 lson o<<1,l,mid#define rson o<<1|1,mid+1,rusing namespace std;const int N=1e5;int llen[N<<2],rlen[N<<2],mlen[N<<2],d[N];int n,m,t,cnt;char c;inline void pushup(int o,int l,int r){ int mid=l+r>>1; llen[o]=llen[o<<1]; rlen[o]=rlen[o<<1|1]; mlen[o]=max(max(mlen[o<<1],mlen[o<<1|1]),rlen[o<<1]+llen[o<<1|1]); if(llen[o<<1]==mid-l+1)llen[o]+=llen[o<<1|1]; if(rlen[o<<1|1]==r-mid)rlen[o]+=rlen[o<<1];}inline void build(int o,int l,int r){ llen[o]=rlen[o]=mlen[o]=r-l+1; if(l==r)return; int mid=l+r>>1; build(lson); build(rson);}inline void update(int o,int l,int r,int x,int c){ if(l==r){llen[o]=rlen[o]=mlen[o]=c;return ;} int mid=l+r>>1; if(x<=mid)update(lson,x,c); else update(rson,x,c); pushup(o,l,r);}inline int query(int o,int l,int r,int x){ if(l==r||!mlen[o]||mlen[o]==r-l+1)return mlen[o]; int mid=l+r>>1; if(x<=mid){ if(x>mid-rlen[o<<1])return query(lson,x)+query(rson,mid+1); else return query(lson,x); } else { if(x<=mid+llen[o<<1|1])return query(lson,mid)+query(rson,x); else return query(rson,x); }}int main(){ ios::sync_with_stdio(false); while(cin>>n>>m){ build(1,1,n); while(m--){ cin>>c; if(c=='D'){cin>>t;d[++cnt]=t;update(1,1,n,t,0);} else if(c=='Q'){cin>>t;cout<<query(1,1,n,t)<<endl;} else {update(1,1,n,d[cnt--],1);} } } return 0;}