参考：https://blog.csdn.net/ophunter_lcm/article/details/9879495
题意：
有n个花瓶，有两种操作，1.从a开始放b朵花，有花的花瓶跳过，2.把a到b间的花全部拿下来。
思路：
线段树+二分
利用二分确定区间，这样就可以是线段树实现更简单的问题：
1）对区间进行全部设置为1的操作
2）对区间进行全部清零的操作
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iterator> using namespace std;
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
#define debug(x) cerr << #x << " = " << x << "\n"; typedef long long ll;
const int maxn = ;
const int mdd = ;
int n,m;
struct node {
int l,r;
int lazy,sum;
}st[maxn<<]; void build(int l,int r,int rt)
{
st[rt].l = l,st[rt].r = r;
st[rt].sum = ;
st[rt].lazy = -;
int mid = (l+r)>>;
if(l==r)return;
build(lson);
build(rson);
}
inline void pushup(int rt)
{
st[rt].sum = st[rt<<].sum + st[rt<<|].sum;
}
inline void pushdown(int rt)
{ if(st[rt].lazy==)
{
st[rt<<].lazy = st[rt<<|].lazy = st[rt].lazy;
st[rt<<].sum = st[rt<<].r - st[rt<<].l + ;
st[rt<<|].sum = st[rt<<|].r - st[rt<<|].l + ;
}
else if(st[rt].lazy==)
{
st[rt<<].lazy = st[rt<<|].lazy = st[rt].lazy;
st[rt<<].sum = st[rt<<|].sum = ;
} st[rt].lazy = -;
}
int query(int l,int r,int rt,int L,int R)
{
if(l>=L&&r<=R)
{
return st[rt].sum;
}
int mid = (l + r)>>;
pushdown(rt);
int ans = ;
if(mid>=L)ans += query(l,mid,rt<<,L,R);
if(mid<R)ans += query(mid+,r,rt<<|,L,R);
return ans;
}
void update(int l,int r,int rt,int L,int R,int op)
{
if(l>=L&&r<=R)
{
if(op==){
st[rt].lazy = ;
st[rt].sum = r - l + ;
}
else {
st[rt].lazy = ;
st[rt].sum = ;
}
return;
}
int mid = (r+l)>>;
pushdown(rt);
if(mid>=L)update(l,mid,rt<<,L,R,op);
if(mid<R)update(mid+,r,rt<<|,L,R,op);
pushup(rt);
}
int bdfind(int st,int len)//二分查找
{
int le = st;
int ri = n;
int ans = -;
while(le <= ri)
{
int mid = (le + ri)>>;
int lenSum = query(,n,,st,mid); //找有花的瓶子个数
if(lenSum + len == mid - st + )
{
ans = mid; //不要直接return,要找最小的。
ri = mid - ;
}
else if(lenSum + len < mid - st +)
{
ri = mid - ;
}
else le = mid + ;
}
return ans;//找到在【st，mid】间符合len个空瓶;
}
int main(){
// freopen("input","r",stdin);
int t;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
build(,n,);
while(m--)
{
int op;
int a,b,c;
scanf("%d%d%d", & op, & a,& b);
if(op==)
{
a++;
int st = bdfind(a,);
if(st==-)
puts("Can not put any one.");
else
{
int tmp = query(,n,,st,n);
tmp = (n - st + ) - tmp; //空瓶个数
b = min(tmp,b);
int ed = bdfind(a, b);
printf("%d %d\n",st-,ed-);
update(,n,,st,ed,);
}
}
else
{
a++,b++;
printf("%d\n",query(,n,,a,b));
update(,n,,a,b,);
}
}
puts("");
}
return ;
}