http://acm.hdu.edu.cn/showproblem.php?pid=4614
线段树的各种操作 写的有点乱 求插入位置是以区间K值的方法求出的 向下更新
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 50010
int s[N<<],lz[N<<];
void build(int l,int r,int w)
{
s[w] = r-l+;
lz[w] = -;
if(l==r)
{
s[w] = ;
return ;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
}
void pushup(int w)
{
s[w] = s[w<<]+s[w<<|];
}
void pushdown(int l,int r,int w)
{
int m = (l+r)/;
if(lz[w]!=-)
{
lz[w<<] = lz[w<<|] = lz[w];
if(lz[w])
{
s[w<<] = m-l+;
s[w<<|] = r-m;
}
else
s[w<<] = s[w<<|] = ;
lz[w] = -;
}
}
int query(int p,int l,int r,int w)
{
if(l==r)
{
return l;
}
pushdown(l,r,w);
int m = (l+r)>>;
if(p<=s[w<<])
return query(p,l,m,w<<);
else
return query(p-s[w<<],m+,r,w<<|);
}
void update(int d,int a,int b,int l,int r,int w)
{
if(a<=l&&b>=r)
{
if(d)
s[w] = r-l+;
else
s[w] = ;
lz[w] = d;
return ;
}
pushdown(l,r,w);
int m = (l+r)>>;
if(a<=m)
update(d,a,b,l,m,w<<);
if(b>m)
update(d,a,b,m+,r,w<<|);
pushup(w);
}
int add(int a,int b,int l,int r,int w)
{
if(a<=l&&b>=r)
{
return s[w];
}
pushdown(l,r,w);
int m = (l+r)>>,re=;
if(a<=m)
re+=add(a,b,l,m,w<<);
if(b>m)
re+=add(a,b,m+,r,w<<|);
return re;
}
int main()
{
int t,n,m,k;
//freopen("1004.in","r",stdin);
//freopen("aa.txt","w",stdout);
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
build(,n-,);
while(m--)
{
int a,b;
scanf("%d%d%d",&k,&a,&b);
if(k==)
{
int ss;
if(a>)
ss = add(,a-,,n-,);
else ss=;
int x = query(ss+,,n-,);
if(s[]-ss<b)
b = s[]-ss;
int y = query(ss+b,,n-,);
if(ss==s[])
printf("Can not put any one.\n");
else
{printf("%d %d\n",x,y);
update(,x,y,,n-,);
}
}
else
{
int sx = add(a,b,,n-,);
//cout<<sx<<" ,"<<endl; if(b>n-)
b = n-;
printf("%d\n",b-a+-sx);
update(,a,b,,n-,);
}
}
puts("");
}
return ;
}