hdu4614 发表于 2018-04-10 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:hdu4614 题解 区间修改线段树,注意是从0开始,具体看代码吧,挺简单的 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#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=1e5;int rt[N<<2],lz[N<<2],n,m,T;inline void pushup(int o){rt[o]=rt[o<<1]+rt[o<<1|1];}inline void pushdown(int o,int len){ if(lz[o]==-1)return ; lz[o<<1]=lz[o<<1|1]=lz[o]; if(!lz[o]){ rt[o<<1]=len-(len>>1); rt[o<<1|1]=len>>1; } else rt[o<<1]=rt[o<<1|1]=0;; lz[o]=-1;}inline void build(int o,int l,int r){ lz[o]=-1; if(l==r){rt[o]=1;return ;} int mid=l+r>>1; build(lson); build(rson); pushup(o);}inline void update(int o,int l,int r,int L,int R){ if(L<=l&&R>=r){rt[o]=0;lz[o]=1;return ;} pushdown(o,r-l+1); int mid=l+r>>1; if(L<=mid)update(lson,L,R); if(R>mid)update(rson,L,R); pushup(o);}inline int clear(int o,int l,int r,int L,int R){ if(L<=l&&R>=r){lz[o]=0;int t=rt[o];rt[o]=r-l+1;return rt[o]-t;} pushdown(o,r-l+1); int mid=l+r>>1,ans=0; if(L<=mid)ans+=clear(lson,L,R); if(R>mid)ans+=clear(rson,L,R); pushup(o); return ans;}inline int query(int o,int l,int r,int L,int R){ if(L>r||R<l)return 0; if(L<=l&&R>=r)return rt[o]; pushdown(o,r-l+1); int mid=l+r>>1,ans=0; if(L<=mid)ans+=query(lson,L,R); if(R>mid)ans+=query(rson,L,R); return ans;}inline int ask(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; int t=query(lson,L,R); if(x<=t)return ask(lson,L,R,x); else return ask(rson,L,R,x-t);}int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); build(1,1,n); while(m--){ int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==1){ int t=query(1,1,n,l+1,n); if(!t)puts("Can not put any one."); else { l=ask(1,1,n,l+1,n,1); r=ask(1,1,n,l,n,min(t,r)); printf("%d %d\n",l-1,r-1); update(1,1,n,l,r); } } else printf("%d\n",clear(1,1,n,l+1,r+1)); } printf("\n"); } return 0;}