链接：http://acm.hdu.edu.cn/showproblem.php?pid=2871
题意：
四种操作：
1.Reset 清空所有内存
2.New x 分配一个大小为x的内存块返回，返回能分配的最小的起始点
3.Free x 释放当前点所在的内存块，并输出左右端点
4.Get x 返回第x个内存块的起始点
讨论每个操作的写法：
第一个操作，把线段树初始化就好了
第二个操作，区间合并的基础操作，
第三个操作：多维护两个数组：st,ed代表当前点所属内存块的左右区间
第四个操作：再开棵树，存每个内存块的起始点，每个起始点下标+1，然后直接找第k大就好了。注意每次2，3，操作内存块发生变化时记得更新这个树上的信息。
题面说了每组数据中间要有空行，不然会PE.
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
#define ls rt<<1
#define rs rt<<1|1
const int M = 1e5 + ;
int lsum[M<<],rsum[M<<],sum[M<<],lazy[M<<],st[M<<],ed[M<<];
int cnt[M<<],cov[M<<],n;
void pushup(int l,int r,int rt){
mid;
lsum[rt] = lsum[ls]; rsum[rt] = rsum[rs];
sum[rt] = max(sum[ls],sum[rs]);
if(lsum[rt] == m-l+) lsum[rt] += lsum[rs];
if(rsum[rt] == r-m) rsum[rt] += rsum[ls];
sum[rt] = max(rsum[ls]+lsum[rs],sum[rt]);
} void pushdown(int l,int r,int rt){
if(lazy[rt]!=-){
mid;
lazy[ls] = lazy[rs] = lazy[rt];
sum[ls] = lsum[ls] = rsum[ls] = (m-l+)*lazy[rt];
sum[rs] = lsum[rs] = rsum[rs] = (r-m)*lazy[rt];
st[ls] = st[rs] = st[rt];
ed[ls] = ed[rs] = ed[rt];
lazy[rt] = -;
}
} void update(int L,int R,int c,int l,int r,int rt){
if(L <= l&&R >= r){
lazy[rt] = c;
lsum[rt] = rsum[rt] = sum[rt] = (r-l+)*c;
if(c) st[rt] = ed[rt] = -;
else{
st[rt] = L; ed[rt] = R;
}
return ;
}
pushdown(l,r,rt);
mid;
if(L <= m) update(L,R,c,lson);
if(R > m) update(L,R,c,rson);
pushup(l,r,rt);
} void rebuild(){
update(,n,,,n,);
//cout<<sum[1]<<endl;
cnt[] = ;
cov[] = ;
} int New(int p,int l,int r,int rt){ //返回空位的左边界
if(l == r) return l;
mid;
pushdown(l,r,rt);
if(sum[ls] >= p) return New(p,lson);
else if(rsum[ls]+lsum[rs]>=p) return m-rsum[ls]+;
else return New(p,rson);
} int Free(int p,int l,int r,int rt){
if(l == r) return rt;
mid;
pushdown(l,r,rt);
if(p <= m) return Free(p,lson);
else return Free(p,rson);
} void up(int rt){
cnt[rt] = cnt[ls] + cnt[rs];
} void down(int rt){
if(cov[rt]){
cnt[ls] = cnt[rs] = ;
cov[ls] = cov[rs] = ;
cov[rt] = ;
}
} int get(int p,int l,int r,int rt){
if(l == r) return l;
mid;
down(rt);
if(cnt[ls] >= p) return get(p,lson);
else return get(p-cnt[ls],rson);
} void change(int p,int c,int l,int r,int rt){
if(l == r){
cnt[rt] = c;
return;
}
down(rt);
mid;
if(p <= m) change(p,c,lson);
else change(p,c,rson);
up(rt);
} int main()
{
int q,k,x;
while(scanf("%d%d",&n,&q)!=EOF){
rebuild();
while(q--){
char op[];
scanf("%s",op);
if(op[] == 'N'){
scanf("%d",&x);
//cout<<sum[1]<<" "<<x<<endl;
if(sum[] < x) printf("Reject New\n");
else{
int k = New(x,,n,);
printf("New at %d\n",k);
change(k,,,n,);
update(k,k+x-,,,n,);
}
}
else if(op[]=='F'){
scanf("%d",&x);
int k = Free(x,,n,);
if(st[k] < ) printf("Reject Free\n");
else{
printf("Free from %d to %d\n",st[k],ed[k]);
change(st[k],,,n,);
update(st[k],ed[k],,,n,);
}
}
else if(op[] == 'R'){
rebuild();
printf("Reset Now\n");
}
else{
scanf("%d",&x);
if(x > cnt[])
printf("Reject Get\n");
else
printf("Get at %d\n",get(x,,n,));
}
}
printf("\n");
}
return ;
}