思路：当k为1的时候，用二分法查询包含有f个空瓶的上界r，然后更新会方便很多，直接更新区间(a,r)了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define lson(x) (x<<1) #define rson(x) ((x<<1)+1) #define mid ((tree[po].l+tree[po].r)>>1) #define inf 1<<30 #define Maxm 1000000 #define Maxn 60000 using namespace std; struct Tree{ int l,r,left,up; }tree[Maxm]; int flag=0,ans,fir; void buildTree(int l,int r,int po) { tree[po].l=l,tree[po].r=r; tree[po].left=r-l+1; tree[po].up=0; if(l==r) return ; buildTree(l,mid,lson(po)); buildTree(mid+1,r,rson(po)); } void down(int po) { if(!tree[po].left) { tree[po].up=0; tree[lson(po)].left=0; tree[rson(po)].left=0; tree[rson(po)].up=0; tree[lson(po)].up=0; return ; } if(!tree[po].up) return ; tree[lson(po)].left=mid-tree[po].l+1; tree[rson(po)].left=tree[po].r-mid; tree[rson(po)].up=1; tree[lson(po)].up=1; tree[po].up=0; } void update(int l,int r,int po) { if(l<=tree[po].l&&r>=tree[po].r) { ans+=tree[po].r-tree[po].l+1-tree[po].left; tree[po].left=tree[po].r-tree[po].l+1; tree[po].up=1; return ; } down(po); if(r<=mid) update(l,r,lson(po)); else if(l>mid) update(l,r,rson(po)); else{ update(l,r,lson(po)); update(l,r,rson(po)); } tree[po].left=tree[lson(po)].left+tree[rson(po)].left; } int findTree(int l,int r,int po) { if(l<=tree[po].l&&r>=tree[po].r) { return tree[po].left; } down(po); int temp=0; if(r<=mid) temp=findTree(l,r,lson(po)); else if(l>mid) temp=findTree(l,r,rson(po)); else{ temp=findTree(l,r,lson(po)); temp+=findTree(l,r,rson(po)); } tree[po].left=tree[lson(po)].left+tree[rson(po)].left; return temp; } void Insert(int l,int r,int po) { if(l<=tree[po].l&&r>=tree[po].r) { if(tree[po].left==tree[po].r-tree[po].l+1&&!flag) flag=1,fir=tree[po].l; if(flag) { tree[po].left=0; return ; } } if(!tree[po].left) return ; down(po); if(r<=mid) Insert(l,r,lson(po)); else if(l>mid) Insert(l,r,rson(po)); else{ Insert(l,r,lson(po)); Insert(l,r,rson(po)); } tree[po].left=tree[lson(po)].left+tree[rson(po)].left; } int main() { int n,m,k,a,b,i,j,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); buildTree(0,n-1,1); for(i=1;i<=m;i++) { scanf("%d%d%d",&k,&a,&b); if(k==1) { flag=0; int l,r,Mid,temp; temp=findTree(a,n-1,1); if(temp<b) b=temp; l=a,r=n-1; while(r>l) { Mid=(l+r)>>1; temp=findTree(a,Mid,1); if(temp>=b) r=Mid; else l=Mid+1; } Insert(a,r,1); if(!flag) printf("Can not put any one. "); else printf("%d %d ",fir,r); } else { ans=0; update(a,b,1); printf("%d ",ans); } } printf(" "); } return 0; }