P2161 [SHOI 2009] 회의장 예약 - 선분 수 염색

#include 
#include 
#include 
#include 
using namespace std;
#define debug(x) cerr << #x << "=" << x << endl;
const int MAXN = 100000 + 10;
typedef long long ll;
int n,m,eff,rig,fail,tag[MAXN * 4],same[MAXN * 4],qx,qy,num,del[MAXN * 4],era;
char cmd[5];
struct segment_tree{
	int val, add;
}tr[MAXN * 4];

struct opts{
	int cmd, st, ed;
}opt[MAXN * 2];

void build(int w, int l, int r) {
	same[w] = 1, tag[w] = 0;
	if(l == r) return;
	int mid = l + r >> 1;
	build(w*2, l, mid);
	build(w*2+1, mid+1, r);
}

void down(int w, int l, int r) {
	same[w] = 0;
	if(!tag[w]) return;
	int le = w * 2, ri = w * 2 + 1; 
	tag[le] = tag[ri] = tag[w];
	tag[w] = 0;
}

void find(int w, int l, int r) {
	if(same[w] == 1) {
		if(!del[tag[w]] && tag[w]) 
			eff--, era++;
		del[tag[w]] = 1;
		tag[w] = num;
		return;
	}
	int le = w * 2, ri = w * 2 + 1; 
	int mid = l + r >> 1;
	find(le, l, mid), find(ri, mid+1, r);
	tag[w] = num, same[w] = 1;
}


void change(int w, int l, int r) {
	if(qx <= l && r <= qy) {
		find(w, l, r);
		return;
	}
	down(w, l, r);
	int le = w * 2, ri = w * 2 + 1; 
	int mid = l + r >> 1;
	if(qx <= mid)
		change(le, l, mid);
	if(qy > mid)
		change(ri, mid+1, r);
}

int main() {
	scanf("%d", &n);
	char cmd[5];
	for(int i=1; i<=n; i++) {
		scanf("%s", cmd);
		if(cmd[0] == 'A') {
			int sta, ed;
			scanf("%d%d", &sta, &ed);
			rig = max(rig, ed);
			opt[i].cmd = 1;
			opt[i].st = sta;
			opt[i].ed = ed;
		} else {
			opt[i].cmd = 2;
		}
	}
	build(1, 1, rig);
	for(int i=1; i<=n; i++) {
		if(opt[i].cmd == 1) {
			int sta = opt[i].st, ed = opt[i].ed;
			eff++;			
			num++;
			era = 0;
			qx = sta, qy = ed;
			change(1, 1, rig);
			printf("%d
", era);
		} else {
			printf("%d
", eff);
		}
	} 
	return 0;
}