hdu3950

线段树即可解决这个题。向线段树插入一个车阵的时候，只需要插入车阵的最左边的点p(姑且称这些点为黑点)即可，

len[p]记录这个车阵的长度（len数组的作用不仅仅是这些，当p这个位置为空白时，len[p]

表示从p位置开始往右的一段空白的长度）。seg结构里的lp,rp,表示区间[l, r]的黑点的位置的最小值和最小值,

sum表示黑点的总和。而minPos有点不一样，minPos表示的是长度在[l, r]之间的连续的空白段的左端点的最小值

(理解这个很重要)。

#include <iostream>
#include <stdio.h>
#include <set>
using namespace std;
const int N =  50005;
const int INF = 0X7FFFFFFF;
struct seg{
	int l, r;
	int lp, rp, minPos;
	int sum;
	bool leaf(){
		return l == r;
	}
	int mid(){
		return (l+r)>>1;
	}
}segs[N<<2];

set<int> pos[N];
int len[N];
int n, q;

template <typename T>
void getNum(T& a){
	a = 0;
	char ch;
	while(true){
		ch = getchar();
		if(ch >= '0' && ch <= '9') break;
	}
	a = ch - '0';
	while(true){
		ch = getchar();
		if(ch < '0' || ch > '9') break;
		a = a * 10 + ch - '0';
	}
}

bool input(){
	scanf("%d%d", &n, &q);
	return true;
}
inline bool check(int i){
	return i >= 1 && i <= n;
}
inline int ls(int id){
	return (id<<1)+1;
}

inline int rs(int id){
	return (id<<1)+2;
}

void build(int id, int l, int r){
	segs[id].l = l; segs[id].r = r;
	segs[id].lp = n+1; segs[id].rp = 0;
	segs[id].minPos = INF; segs[id].sum = 0;
	if(l < r){
		int mid = segs[id].mid();
		build(ls(id), l, mid);
		build(rs(id), mid+1, r);
	}else{
		pos[l].clear();
	}
}

void insBlank(int id, int p, int tlen, bool flag){
	//flag为true表示添加，为false表示删除
	//在p位置插入(删除)一段长度为tlen的空白段。
	if(segs[id].leaf()){
		if(flag){
			pos[tlen].insert(p);
			len[p] = tlen;
		}else{
			pos[tlen].erase(p);
		}
		if(pos[tlen].size() > 0){
			segs[id].minPos = *pos[tlen].begin();
		}else{
			segs[id].minPos = INF;
		}
		return ;
	}
	if(tlen <= segs[id].mid()){
		insBlank(ls(id), p, tlen, flag);
	}else{
		insBlank(rs(id), p, tlen, flag);
	}

	segs[id].minPos = min(segs[ls(id)].minPos, segs[rs(id)].minPos);
}

void insCars(int id, int p, bool flag){
	//flag为true表示添加，为false表示删除
	//在位置p插入(或删除)一个黑点
	if(segs[id].leaf()){
		if(flag){
			segs[id].sum++;
		}else{
			segs[id].sum--;
		}
		if(segs[id].sum == 0){
			segs[id].lp = n+1;
			segs[id].rp = 0;
		}else{
			segs[id].lp = segs[id].l;
			segs[id].rp = segs[id].l;
		}
		return ;
	}
	if(p <= segs[id].mid()){
		insCars(ls(id), p, flag);
	}else{
		insCars(rs(id), p, flag);
	}
	segs[id].sum = segs[ls(id)].sum + segs[rs(id)].sum;
	segs[id].lp = min(segs[ls(id)].lp, segs[rs(id)].lp);
	segs[id].rp = max(segs[ls(id)].rp, segs[rs(id)].rp);
}

int qryBlank(int id, int l, int r){  //查询长度在[l, r]之间的空白段的起点的最小值
	if(l <= segs[id].l && segs[id].r <= r){
		return segs[id].minPos;
	}
	if(segs[id].leaf()) return INF;
	int mid = segs[id].mid();
	if(r <= mid) return qryBlank(ls(id), l, r);
	else if(l > mid) return qryBlank(rs(id), l, r);
	else{
		return min(qryBlank(ls(id), l, r), qryBlank(rs(id), l, r));
	}
}
int getl(int id, int l, int r){  //获取区间[l,r]最左的黑点的位置
	if(l <= segs[id].l && segs[id].r <= r){
		return segs[id].lp;
	}
	if(segs[id].leaf()) return n+1;
	int mid = segs[id].mid();
	if(r <= mid) return getl(ls(id), l, r);
	else if(l > mid) return getl(rs(id), l, r);
	else return min(getl(ls(id), l, r), getl(rs(id), l, r));
}
int getr(int id, int l, int r){ //取区间[l,r]最右的黑点的位置
	if(l <= segs[id].l && segs[id].r <= r){
		return segs[id].rp;
	}
	if(segs[id].leaf()) return 0;
	int mid = segs[id].mid();
	if(r <= mid) return getr(ls(id), l, r);
	else if(l > mid) return getr(rs(id), l, r);
	else return max(getr(ls(id), l, r), getr(rs(id), l, r));
}

int getPos(int m, int l, int r){
	if(m > n) return INF;
	if(segs[0].sum == 0){
		return 1;
	}
	int pos;
	pos = segs[0].lp;
	if(pos - 1 >= m){
		return max(pos - r - m, 1);
	}
	pos = qryBlank(0, m, m+l+r);
	if(pos <= n){
		int tr = getl(0, pos, n);
		if(tr < 1) tr = n + 1;

		if(tr < n+1){ //右边还有车阵
			pos = max(pos, tr-r-m);
		}
		return pos;
	}
	pos = segs[0].rp + len[segs[0].rp] - 1;
	if(n - pos >= m){
		return pos+1;
	}
	return INF;
}

void ins(int p, int m, bool flag){  //flag为true表示插入一排车，为false表示离开
	int l, r;
	if(p == 1){
		l = 0;
	}else{
		l = getr(0, 1, p - 1);
		if(!check(l)) l = 0;
		else{
			l = l + len[l] - 1;
		}
	}
	if(p+m-1 == n){
		r = n+1;
	}else{
		r = getl(0, p+m, n);
		if(!check(r)) r = n+1;
	}
	if(r-l-1 > 0){
		insBlank(0, l+1, r-l-1, !flag);
	}
	if(p-l-1 > 0){
		insBlank(0, l+1, p-l-1, flag);
	}
	if(r-p-m > 0){
		insBlank(0, p+m, r-p-m, flag);
	}
}
int qrykth(int id, int k){ //查询第k个黑点的位置
	if(segs[id].leaf()) return segs[id].l;
	if(segs[ls(id)].sum >= k) return qrykth(ls(id), k);
	return qrykth(rs(id), k-segs[ls(id)].sum);
}
int cnt = 0;
void solve(){
	build(0, 1, n);
	insBlank(0, 1, n, true);
	int i, m, l, r, k;
	char op[3];
	printf("Case #%d:\n", ++cnt);
	for(i = 1; i <= q; i++){
		scanf("%s", op);
		if(op[0] == 'A'){
			getNum(m);
			getNum(l);
			getNum(r);
			int p;
			p = getPos(m, l, r);
			if(p <= n){
				printf("%d\n", p);
				ins(p, m, true);
				insCars(0, p, true);
				len[p] = m;
			}else{
				printf("-1\n");
			}
		}else{
			getNum(k);
			if(k <= segs[0].sum){
				int p = qrykth(0, k);
				ins(p, len[p], false);
				insCars(0, p, false);
			}
		}
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while(t--){
		input();
		solve();
	}
	return 0;
}