<题目链接>
题目大意：
有n个花瓶，每个花瓶中只能放一朵花。两种操作，一种是从A开始放F朵花，如果有的花瓶中已经有花则跳过这个花瓶，往下一个花瓶放；第二种是将区间[A,B]之间花瓶中的花清空。如果是第一种操作，输出这次放的花的左右端点；如果是第二种操作，输出这次总共清理出了多少支花。
解题分析：
本题可以很巧妙的将这两种操作全部转化为区间修改，毫无疑问，第二种操作肯定是区间修改；对于第一种操作，可以用二分答案将x后的第num个空瓶的坐标查找出来，因为二分答案时需要直接查询指定区间内空瓶的数量，所以线段树叶子节点维护一个值，代表该区间空瓶的数量，得到第一个和最后一个空瓶的数量后，直接对该区间进行区间修改，将空瓶数量全部置0即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define Lson rt<<1,l,mid
#define Rson rt<<1|1,mid+1,r
const int M =5e4+;
int n,m;
int tr[M<<],lazy[M<<];
//lazy[rt]初始化为-1，lazy[rt]==0,代表这个区间瓶子全满,lazy[rt]==1,代表这个区间瓶子全空
void Pushup(int rt){ tr[rt]=tr[rt<<]+tr[rt<<|]; }
void Pushdown(int rt,int len){
if(lazy[rt]!=-){
int tmp=lazy[rt];
lazy[rt<<]=tmp;
lazy[rt<<|]=tmp;
tr[rt<<]=(len-(len>>))*tmp;
tr[rt<<|]=(len>>)*tmp;
lazy[rt]=-;
}
}
void build(int rt,int l,int r){
lazy[rt]=-;
if(l==r){
tr[rt]=;
return;
}
int mid=(l+r)>>;
build(Lson);
build(Rson);
Pushup(rt);
}
void update(int rt,int l,int r,int L,int R,int c){
if(L<=l&&r<=R){
lazy[rt]=c;
tr[rt]=(r-l+)*c;
return;
}
Pushdown(rt,r-l+);
int mid=(l+r)>>;
if(L<=mid)update(Lson,L,R,c);
if(R>mid)update(Rson,L,R,c);
Pushup(rt);
}
int query(int rt,int l,int r,int L,int R){ //查询指定区间的空瓶数量
if(L<=l&&r<=R)return tr[rt];
Pushdown(rt,r-l+);
int mid=(l+r)>>;
int ans=;
if(L<=mid)ans+=query(Lson,L,R);
if(R>mid)ans+=query(Rson,L,R);
return ans;
}
int bin_search(int x,int num){ //二分答案，查找从x开始的第num个空瓶子的下标
int l=x,r=n,ans;
while(l<=r){
int mid=(l+r)>>;
if(query(,,n,x,mid)>=num)ans=mid,r=mid-;
else l=mid+;
}
return ans;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
build(,,n);
while(m--){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==){
x++; //由于线段树叶子节点习惯从1~n开始存储，所以a++
int cnt=query(,,n,x,n); //查询这个区间的空瓶子数量
if(cnt==)printf("Can not put any one.\n");
else{ //二分查找第一个空瓶子和最后一个空瓶子的下标
int le=bin_search(x,);
int ri=bin_search(x,min(cnt,y));
update(,,n,le,ri,);
printf("%d %d\n",le-,ri-);
}
}
else{
x++,y++;
printf("%d\n",y-x+-query(,,n,x,y));
update(,,n,x,y,);
}
}
printf("\n");
}
return ;
}
2018-09-29