摘要：
如果你能放但不能放所有的花，输出n是很好的。第二种方法是在间隔[A，B]之间清空花瓶中的花。输出这次清除了多少花。思路：第二种方法显然可以用线段树来实现。第一个是如何使用线段树通过二分法和线段树确定右端点的位置。这样，第一个操作是间隔更新，并使用namespacestd#definelllong#definepbpush_back#definempmake_pair#definelsonl，mid，rt˂˂1#definersonmid+1，r，rt˂˂1|1#definefirst#definesecondconstintN=5E4+3；常数M=5e4+3；整数，m；整数和[N˂˂2]，fst[N˂˂2]，las[N˂˂02]，L[N˂[2]，R[N˂2]；整数[N˂˂2]；//第一个开始空las最后一个空和空数量void pushup｛sum[rt]=sum[rt˂˂1]+sum[rt˂˂1|1]；如果（las[rt˂˂1|1]！
题意：有n个花瓶，每个花瓶中只能放一朵花。
两种操作，一种是从A开始放F朵花，如果有的花瓶中已经有花则跳过这个花瓶，往下一个花瓶放；
输出这次放的花的左右端点。如果能放但是放不完f朵输出n就好了
第二种是将区间[A,B]之间花瓶中的花清空。输出这次总共清理出了多少支花。
思路：第二种很明显可以用线段树实现，问题在第一种如何用线段树实现
用二分 和 线段树 来判断右端点的位置 这样就可以了 第一次操作就成了区间更新
并且查询左右端点
#include<cstdio>#include<cstring>#include<iostream>#include<vector> using namespacestd; #define ll long long #define pb push_back #define mp make_pair #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define fi first #define se second const int N = 5E4+3; const int M = 5e4+3; intn,m; int sum[N<<2],fst[N<<2],las[N<<2],L[N<<2],R[N<<2]; int col[N<<2]; //fst 开始空的 las最后空的 sum 空的数量 void pushup(intrt){ sum[rt] = sum[rt<<1]+sum[rt<<1|1]; if(las[rt<<1|1]!=-1) las[rt]=las[rt<<1|1]; else las[rt]=las[rt<<1]; if(fst[rt<<1]!=-1) fst[rt]=fst[rt<<1]; else fst[rt] = fst[rt<<1|1]; R[rt] = R[rt<<1|1]; L[rt] = L[rt<<1]; } void pushdown(intrt){ //添加 if(col[rt]==1){ col[rt<<1]=col[rt<<1|1] =col[rt]; sum[rt<<1] = 0; sum[rt<<1|1] = 0; las[rt<<1]=las[rt<<1|1] = -1; fst[rt<<1]=fst[rt<<1|1] =-1; col[rt]=0; } else if(col[rt]==-1){ col[rt<<1]=col[rt<<1|1] =col[rt]; sum[rt<<1] = R[rt<<1]-L[rt<<1]+1; sum[rt<<1|1] = R[rt<<1|1]-L[rt<<1|1]+1; las[rt<<1] = R[rt<<1]; fst[rt<<1] = L[rt<<1]; las[rt<<1|1] = R[rt<<1|1]; fst[rt<<1|1] = L[rt<<1|1]; col[rt]=0; } } void build(int l,int r,intrt){ col[rt] =0; if(l==r){ L[rt] =r; R[rt] =l; sum[rt]=1; las[rt]=r; fst[rt]=l; return; } int mid = (l+r)/2; build(lson);build(rson); pushup(rt); } void update(int l,int r,int rt, int a,int b,intval){ if(a<=l && b>=r){ if(val==1){ if(sum[rt] ==0)return; col[rt] =val; sum[rt] = 0; las[rt]=fst[rt]=-1; } else if(val==-1){ if(sum[rt]==R[rt]-L[rt]+1)return; //printf("%d %d %d %d %d %d ",l,r,rt,a,b,sum[rt]); col[rt]=val; sum[rt]= R[rt]-L[rt]+1; las[rt]=R[rt]; fst[rt]=L[rt]; //printf("gai: %d %d %d %d %d %d ",l,r,rt,a,b,sum[rt]); } return; } pushdown(rt); int mid=(l+r)/2; if( a<=mid ) update(lson,a,b,val); if( b>mid ) update(rson ,a,b,val); pushup( rt ); } int qfst(int l,int r,int rt,int a,intb){ if(a<=l && b>=r){ returnfst[rt]; } pushdown(rt); int mid =(l+r)/2; if(b<=mid)returnqfst(lson,a,b); else if( a>mid )returnqfst(rson,a,b); else{ int ans1=-1; if(a<=mid) ans1 =qfst(lson,a,b); if(ans1!=-1)returnans1; if(b>mid) returnqfst(rson,a,b); } } int qlst(int l,int r,int rt,int a,intb){ if(a<=l && b>=r){ returnlas[rt]; } pushdown(rt); int mid =(l+r)/2; if(b<=mid)returnqlst(lson,a,b); else if(a>mid)returnqlst(rson,a,b); else{ int ans1=-1; if(b>mid) ans1=qlst(rson,a,b); if(ans1!=-1)returnans1; if(a<=mid)returnqlst(lson,a,b); } } int qnum(int l,int r,int rt,int a,intb){ if(a<=l && b>=r){ //printf("get :%d %d %d %d %d %d ",l,r,rt,a,b,sum[rt]); int res =sum[rt]; returnres; } pushdown(rt); int ans = 0; int mid =(l+r)/2; if(a<=mid) ans+=qnum(lson,a,b); if(b>mid) ans+=qnum(rson,a,b); returnans; } int b_s(int st,intneed){ int l=st,r=n; int res = qnum(1,n,1,st,n); if(res==0)return -1; if(res<need)returnn; int ans =n; while(l<=r){ int m = (l+r)/2; if(qnum(1,n,1,st,m)>=need){ ans =min(ans,m); r=m-1; } else l= m+1; } returnans; } intmain(){ intt; cin>>t; intop; while(t--){ scanf("%d %d",&n,&m); build(1,n,1); while(m--){ scanf("%d",&op); if(op==1){ int x,f;scanf("%d %d",&x,&f); x++; int v =b_s(x,f); if(v==-1){ printf("Can not put any one. "); } else{ printf("%d %d ",qfst(1,n,1,x,v)-1 ,qlst(1,n,1,x,v)-1); update(1,n,1,x,v,1); } } else if(op==2){ int a,b;scanf("%d %d",&a,&b); a++;b++; int res = qnum(1,n,1,a,b); printf("%d ",b-a+1-res); update(1,n,1,a,b,-1); //cout<<sum[24]<<"!!"<<endl; res = qnum(1,n,1,a,b); //printf("update : %d ",b-a+1-res); } } cout<<endl; } return 0; }