比赛的时候一直想用树状数组，但是树状数组区间更新之后，功能有局限性。线段树中的lz标记很强大，这个题的题意也挺纠结的。
k = 1时，从a开始，插b个花，输出第一个插的位置，最后一个的位置，一个都没插，输出不能插。
k = 2时，将[a,b]区间都清空，输出这个区间上本来有多少朵花。
主要是k = 1的时候，很难弄。给出区间[a,b]要找到第一个空花瓶，空花瓶的个数 = 总的-插花的个数
这肯定是一个单增的，所以利用二分求下界，这个位置，就是第一个空花瓶的位置，最后一个花瓶的位置需要特判一下，确定是第几个空花瓶，剩下的跟算第一个差不多。
主要是很多细节要注意,写代码要各种严谨....
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cstdlib>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[*];
int lz[*];
int n;
void pushup(int rt)
{
sum[rt] = sum[rt<<] + sum[rt<<|];
}
void pushdown(int rt,int m)
{
if(lz[rt] == )
{
lz[rt<<] = lz[rt];
lz[rt<<|] = lz[rt];
sum[rt<<] = (m - (m>>));
sum[rt<<|] = (m>>);
lz[rt] = ;
}
else if(lz[rt] == -)
{
lz[rt<<] = lz[rt];
lz[rt<<|] = lz[rt];
sum[rt<<] = ;
sum[rt<<|] = ;
lz[rt] = ;
}
}
int query(int L,int R,int l,int r,int rt)
{
int m;
int ans = ;
if(l >= L&&r <= R)
{
return sum[rt];
}
pushdown(rt,r-l+);
m = (l+r)>>;
if(L <= m) ans += query(L,R,lson);
if(R > m) ans += query(L,R,rson);
return ans;
}
void update(int L,int R,int sc,int l,int r,int rt)
{
int m;
if(l >= L&&r <= R)
{
lz[rt] = sc;
if(sc == )
sum[rt] = (r - l + );
else
sum[rt] = ;
return ;
}
pushdown(rt,r-l+);
m = (l+r) >> ;
if(L <= m) update(L,R,sc,lson);
if(R > m) update(L,R,sc,rson);
pushup(rt);
}
int bis(int x,int key)
{
int str,end,mid,temp;
str = x,end = n-;
if(end-x+ - query(x,end,,n-,) == )
return -;
while(str < end)
{
mid = (str + end)/;
temp = (mid-x+) - query(x,mid,,n-,);
if(temp < key)
str = mid + ;
else
end = mid;
}
return str;
}
int bin(int x,int key)
{
int str,end,mid,temp;
str = x;end = n-;
temp = (n-x) - query(x,n-,,n-,);
if(key > temp)
key = temp;
while(str < end)
{
mid = (str + end)/;
temp = (mid-x+) - query(x,mid,,n-,);
if(temp < key)
str = mid + ;
else
end = mid;
}
return str;
}
int main()
{
int t,m,i,a,b,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(sum,,sizeof(sum));
memset(lz,,sizeof(lz));
for(i = ;i <= m;i ++)
{
scanf("%d%d%d",&k,&a,&b);
if(k == )
{
a = bis(a,);
if(a != -)
b = bin(a,b);
if(a == -)
printf("Can not put any one.\n");
else
{
printf("%d %d\n",a,b);
update(a,b,,,n-,);
}
}
else
{
printf("%d\n",query(a,b,,n-,));
update(a,b,-,,n-,);
}
}
printf("\n");
}
return ;
}