P - Vases and Flowers （线段树&二分）

P - Vases and Flowers （线段树&二分）

思路：给定n个花瓶，m个操作，1：从L开始插F朵花，给花瓶中花为0的插入花，插入到不能插入为止。2：区间求和，并清零。
第二个操作简单，第一个操作要用到二分，查找最左端第一个插入花的位置和最后一个插入花位置。

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct node{ //结构体线段树板子. 
	int l,r,s,lz;//[l,r],sum,lzay tag 
}a[N];
void re(int x){ //refresh 更新和sum 
	a[x].s=a[x<<1].s+a[x<<1|1].s; 
}
void pushdown(int x){ //下放标记. 
	if(~a[x].lz){
		a[x<<1].lz=a[x<<1|1].lz=a[x].lz;
		a[x<<1].s=(a[x<<1].r-a[x<<1].l+1)*a[x].lz;
		a[x<<1|1].s=(a[x<<1|1].r-a[x<<1|1].l+1)*a[x].lz;
		a[x].lz=-1;
	}
}
void build(int x,int l,int r){
	a[x].l=l,a[x].r=r,a[x].lz=-1;//lzay tag初始化为-1 便于后面修改为0和1. 
	if(l==r) return;
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
} 
void update(int x,int l,int r,int val){  ///update和query都需要pushdown 
	 if(l<=a[x].l&&a[x].r<=r){ //更新. 
	 	 a[x].s=(a[x].r-a[x].l+1)*val;
		 a[x].lz=val;
		 return; 
	 }
	 pushdown(x);
	 int mid=(a[x].l+a[x].r)>>1;
	 if(l<=mid) update(x<<1,l,r,val);
	 if(r>mid) update(x<<1|1,l,r,val);
	 re(x);
}
int  query(int x,int l,int r){
	 if(l<=a[x].l&&a[x].r<=r) return a[x].s;
	 else if(a[x].r<l||a[x].l>r) return 0;
	 pushdown(x);
	 int mid=(a[x].l+a[x].r)>>1;
	 return query(x<<1,l,r)+query(x<<1|1,l,r);
}
int fun(int st,int ed,int val){//二分[st,ed]0个数为val的最小右端点. 
	int l=st,r=ed;
	while(l<=r){
		int mid=(l+r)>>1;
		if(mid-st+1-query(1,st,mid)>=val) r=mid-1;//[st,mid]区间中0的个数. 
		else l=mid+1;
	}
	return l;
} 
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(a,0,sizeof a);
		int n,m;
		scanf("%d%d",&n,&m);
		build(1,1,n);
		while(m--){
			int op,x,y;
			scanf("%d%d%d",&op,&x,&y);
			x++;//改成从[1,n]的区间. 
			if(op==1){
				 int cnt=n-x+1-query(1,x,n);//剩下未被插花的花瓶数 
				 if(!cnt){
				 	puts("Can not put any one.");
				 	continue;
				 }
				 int l=fun(x,n,1),r=fun(x,n,min(y,cnt));
				 printf("%d %d\n",l-1,r-1);
				 update(1,l,r,1);
			}
			else y++,printf("%d\n",query(1,x,y)),update(1,x,y,0);
		}
		puts("");
	}
	return 0;
}