题目
0到n-1的花瓶，操作1在下标a开始插b朵花，输出始末下标。操作2清空[a,b]的花瓶，求清除的花的数量。
线段树懒惰标记来更新区间。
操作1，先查询0到a-1有num个空瓶子，然后用线段树的性质，或者二分找出第num+1个空瓶子的下标，和第num+b个空瓶子的下标。再区间更新为满。
操作2，也相当于区间更新为空。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50001
using namespace std;
int tree[N<<],lz[N<<];
void PushUp(int node)
{
tree[node]=tree[node<<]+tree[node<<|];
}
void PushDown(int node,int v)
{
if(lz[node]==)tree[node<<]=tree[node<<|]=;//清空区间
else if(lz[node]==)//填满区间
{
tree[node<<]=v-(v>>);//左儿子的区间长度
tree[node<<|]=v>>;
}
lz[node<<]=lz[node<<|]=lz[node];//将懒惰标记下移
lz[node]=;
}
void build(int l,int r,int node)
{
lz[node]=tree[node]=;
if(l==r)return;
int m=l+r>>;
build(l,m,node<<);
build(m+,r,node<<|);
}
//查询[ll,rr]有多少花。节点node对应区间[l,r]
int query(int l,int r,int node,int ll,int rr)
{
if(r<ll||l>rr)return ;//[l,r]不在[ll,rr]范围内
if(ll<=l&&r<=rr)return tree[node];//[l,r]完全在[ll,rr]范围内
if(lz[node])PushDown(node,r-l+);//将懒惰标记下移
int m=l+r>>;
return query(l,m,node<<,ll,rr)+query(m+,r,node<<|,ll,rr);
}
void update(int l,int r,int node,int ll,int rr)
{
if(r<ll||l>rr)return;
if(ll<=l&&r<=rr)
{
tree[node]=r-l+;//区间填满
lz[node]=;//标记为需要填满子区间，直接覆盖原来的懒惰标记
}
else
{
if(lz[node])PushDown(node,r-l+);//先将原有的标记下移
int m=l+r>>;
update(l,m,node<<,ll,rr);
update(m+,r,node<<|,ll,rr);
PushUp(node);
}
}
//找出第v个空瓶子的下标
int solve(int l,int r,int node,int v)
{
if(l==r) return l;
if(lz[node])PushDown(node,r-l+);
int m=l+r>>;
int ans=m-l+-tree[node<<];//左儿子区间有多少空瓶子
if(ans<v) return solve(m+,r,node<<|,v-ans);
return solve(l,m,node<<,v);
}
int dele(int l,int r,int node,int ll,int rr)
{
if(r<ll||l>rr)return ;
int ans=;
if(ll<=l&&r<=rr)
{
ans=tree[node];//要清除的花
tree[node]=;
lz[node]=;
}
else
{
if(lz[node])PushDown(node,r-l+);
int m=l+r>>;
ans=dele(l,m,node<<,ll,rr)+dele(m+,r,node<<|,ll,rr);
PushUp(node);
}
return ans;
}
int main()
{
int t,n,m,k,a,b,ansl,ansr;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
build(,n-,);
for(int i=; i<m; i++)
{
scanf("%d%d%d",&k,&a,&b);
if(k==)
{
int sum=query(,n-,,a,n-);//求a到n-1有多少花
if(sum==n-a) printf("Can not put any one.\n");//如果满了就不能插了
else
{
int num=a-query(,n-,,,a-);//0到a-1有多少空瓶子
ansl=solve(,n-,,num+);//第num+1个空瓶子的下标
ansr=solve(,n-,,min(num+b,num+n-a-sum));//第num+b个空瓶子的下标
printf("%d %d\n",ansl,ansr);
update(,n-,,ansl,ansr);
}
}
else printf("%d\n", dele(,n-,,a,b));
}
printf("\n");
}
}