很恶心的区间查询更新题目。
两个操作，一个是向给定的l向后插入k个元素，输出插入的起始点和结束点；一个是将l和r之间的部分清0，输出清0个数。
这里更新的操作很好完成，查询的就比较恶心了，写了三个查询函数，分别查询从l开始第一个空的位置，从l开始第k个空的位置，以及查询区间有多少被占用的位置。
第一个查询很好完成，先序遍历加上记录区间有多少可用点，找到第一个可用的就可以返回了。
第二个比较恶心，有可能存在给定的数量无法完全插入的情况，这是就要先查询一下l之后有多少可用的点，然后再和给的比较，大于等于就能全部插入，就依次查询即可，小于则不能完全插入，最多只能插入剩余的数量个，然后查询的时候注意判断，找到最后一个元素的位置即可。
第三个查询就查询一下区间内有多少被占用的点，很好写。
附代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
using namespace std;
const int MAX=50000+10;
int sum1[MAX<<2]; //0代表这个位置可用，1代表这个位置不可用
int sum2[MAX<<2]; //0代表不可用，1代表可用
int rank[MAX<<2]; //延迟标记
int ansl;
int ansr;
int n,m;
void pushup(int rt)
{
sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1];
sum2[rt]=sum2[rt<<1]+sum2[rt<<1|1];
return ;
}
void pushdown(int l,int r,int rt)
{
if (rank[rt]!=-1)
{
delf;
if (rank[rt]==1)
{
sum1[rt<<1]=m-l+1;
sum2[rt<<1]=0;
sum1[rt<<1|1]=r-m;
sum2[rt<<1|1]=0;
}
else
{
sum2[rt<<1]=m-l+1;
sum1[rt<<1]=0;
sum2[rt<<1|1]=r-m;
sum1[rt<<1|1]=0;
}
rank[rt<<1]=rank[rt<<1|1]=rank[rt];
rank[rt]=-1;
}
return ;
}
void build(int l,int r,int rt)
{
rank[rt]=-1;
if (l==r)
{
sum1[rt]=0;
sum2[rt]=1;
return ;
}
delf;
build (lson);
build (rson);
pushup(rt);
return ;
}
void update(int L,int R,int v,int l,int r,int rt) //1代表占用，0代表不占用
{
if (L<=l&&r<=R)
{
int len=(r-l+1);
sum1[rt]=v*len;
sum2[rt]=(1-v)*len;
rank[rt]=v;
return ;
}
pushdown(l,r,rt);
delf;
if (L<=m)
update(L,R,v,lson);
if (R>m)
update(L,R,v,rson);
pushup(rt);
return ;
}
void query1(int L,int l,int r,int rt)
{
if (L<=l&&l==r)
{
if (sum2[rt]==1) //如果找到了，直接返回
ansl=l;
return ;
}
delf;
pushdown(l,r,rt);
if (L<=m&&sum2[rt<<1]>0) //查找左区间
query1(L,lson);
if (ansl==-1&&sum2[rt<<1|1]>0) //如果左区间没查找到，查找右区间
query1(L,rson);
return ;
}
int query2(int L,int s,int l,int r,int rt)
{
if (L<=l&&sum2[rt]<s) //如果给的数量大于区间剩余数，则肯定在这个区间右边，要把这部分减去
return sum2[rt];
if (L<=l&&l==r&&sum2[rt]==1) //如果查找到了，则直接返回
{
ansr=l;
return -1;
}
delf;
pushdown(l,r,rt);
if (L<=l&&sum2[rt]>=s) //如果L<=l且s<小于这个区间的空点数，那么肯定在这个区间，就是这个区间内玩耍了~
{
if (sum2[rt<<1]<s) //左边不够用，肯定在右边
query2(L,s-sum2[rt<<1],rson);
else
query2(L,s,lson); //否则左边够用，在左边
pushup(rt);
return -1;
}
if (m>=L) //如果l<L，那么就比较麻烦了，先查l到m，如果l到m包含L的话，就有可能存在解。
{
int s1=query2(L,s,lson); //查找左孩子
int s2;
if (s1!=-1) //左孩子没查到
s2=query2(L,s-s1,rson); //查找右孩子
pushup(rt);
if (s2==-1) //右孩子找到了，就return
return -1;
else
return s1+s2; //否则返回这个区间总共有多少个空点，用s减去这些空点就是这个区间右边的区间需要的空点数
}
else //如果m<L，那么左边已经不可能了，直接查找右孩子
{
int t=query2(L,s,rson);
pushup(rt);
return t;
}
}
int query(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
return sum1[rt];
delf;
pushdown(l,r,rt);
int s=0;
if (m>=L)
s+=query(L,R,lson);
if (R>m)
s+=query(L,R,rson);
pushup(rt);
return s;
}
int main()
{
int T;
scanf("%d",&T);
for (int r=1;r<=T;r++)
{
scanf("%d%d",&n,&m);
build(0,n-1,1);
while (m--)
{
int p,a,b;
scanf("%d%d%d",&p,&a,&b);
if (p==1)
{
ansl=ansr=-1;
if (b>0)
{
int s=query(a,n-1,0,n-1,1);
s=(n-a-s);
if (s==0)
{
printf("Can not put any one.\n");
continue ;
}
query1(a,0,n-1,1);
if (s>=b) //如果剩余点数大于等于b个
int t=query2(a,b,0,n-1,1);
else //如果小于b个
int t=query2(a,s,0,n-1,1);
printf("%d %d\n",ansl,ansr);
update(ansl,ansr,1,0,n-1,1);
}
else
{
printf("Can not put any one.\n");
continue ;
}
}
else
{
printf("%d\n",query(a,b,0,n-1,1));
update(a,b,0,0,n-1,1);
}
}
printf("\n");
}
}