P2161 [SHOI2009]会场预约 - 线段树染色

是真的染色，把不同预约看做不同颜色，现在问题就是一个区间内不同颜色的数量，这个分块线段树都能做吧（不考虑复杂度用莫队也行）
注意，线段树的最大边界必须是定值，不能随输入改变（一开始懒得离线动态更新右端点然后节点的编号就串了）
注意数组大小，因为same和tag数组都是针对线段树节点设置的，所以其数组大小也要开4倍

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
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("%dn", era);
} else {
printf("%dn", eff);
}
}
return 0;
}

最后

以上就是会撒娇乐曲为你收集整理的P2161 [SHOI2009]会场预约 - 线段树染色的全部内容，希望文章能够帮你解决P2161 [SHOI2009]会场预约 - 线段树染色所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。