题解思路：
线段树用来记录空花瓶的个数
对于每次添加花的操作 二分查找L R
删除花的个数用 l-r+1-区间空花瓶数
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<queue> #include<stack> #include<map> #define lson l,mid,now<<1 #define rson mid+1,r,now<<1|1 #define ls now<<1 #define rs now<<1|1 #define all left,right,c #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long const int maxn=1e5+10; using namespace std; int tree[4*maxn],lazy[4*maxn];///存空花1瓶书 void built(int l,int r,int now) { int mid=(l+r)>>1; lazy[now]=-1; if(l==r) { tree[now]=1; return ; } built(lson); built(rson); tree[now]=tree[ls]+tree[rs]; } void pushdown(int l,int r,int now) { int mid=(l+r)>>1; tree[ls]=(mid-l+1)*lazy[now]; tree[rs]=(r-mid)*lazy[now]; lazy[ls]=lazy[rs]=lazy[now]; lazy[now]=-1; } void updata(int l,int r,int now,int left,int right,int c) { int mid=(l+r)>>1; if(left<=l&&r<=right) { tree[now]=(r-l+1)*c; lazy[now]=c; return ; } if(lazy[now]!=-1) pushdown(l,r,now); if(left<=mid) updata(lson,all); if(right>mid) updata(rson,all); tree[now]=tree[ls]+tree[rs]; } int query(int l,int r,int now,int left,int right) { int mid=(l+r)>>1; if(left<=l&&r<=right) { return tree[now]; } if(lazy[now]!=-1) pushdown(l,r,now); int ans=0; if(left<=mid) ans+=query(lson,left,right); if(right>mid) ans+=query(rson,left,right); return ans; tree[now]=tree[ls]+tree[rs]; } int bin_s(int st,int ed,int mub) { int mid,l=st,r=ed; while(l<=r) { mid=(l+r)>>1; int t=query(1,ed,1,st,mid); if(t>=mub) { r=mid-1; } else l=mid+1; } return l; } int main(){ int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); built(1,n,1); for(int i=1;i<=m;i++) { int cmd,a,b; scanf("%d%d%d",&cmd,&a,&b); if(cmd==1) { a++; int t=query(1,n,1,a,n); if(t==0) { printf("Can not put any one. "); } else { int L=bin_s(a,n,1); int R=bin_s(L,n,min(b,t)); updata(1,n,1,L,R,0); printf("%d %d ",L-1,R-1); } } else { a++,b++; int ans=query(1,n,1,a,b); printf("%d ",b-a+1-ans); updata(1,n,1,a,b,1); } } printf(" "); } return 0; }