## 【2017ACM-ICPC广西邀请赛】Color it

【2017ACM-ICPC广西邀请赛】Color it

【动态线段树】

Solution:

C++代码：

```#include <iostream>
#include <cstring>

using namespace std;

const int INF = 1e7;
const int LIM = 2e6;
bool flag;
int tree[LIM], rootPos[51], lrt[LIM], rrt[LIM], num;

inline int mini(int a, int b) {
return a < b ? a : b;
}

inline void clear() {
num = 0;
for (int i = 0; i < LIM; i++) tree[i] = INF;
memset(rootPos, 0, sizeof rootPos);
memset(lrt, 0, sizeof lrt);
memset(rrt, 0, sizeof rrt);
}

inline void pushup(int rt) {
tree[rt] = mini(tree[lrt[rt]], tree[rrt[rt]]);
}

void update(int l, int r, int si, int x, int &rt) {
if (l > si || r < si) return;
if (!rt) rt = ++num;
if (l == r) {
if (tree[rt] > x) tree[rt] = x;
return;
}
int mid = (l + r) >> 1;
update(l, mid, si, x, lrt[rt]);
update(mid + 1, r, si, x, rrt[rt]);
pushup(rt);
}

void query(int l, int r, int qs, int qe, int x, int &rt) {
if (!rt || flag || l > qe || r < qs) return;
if (l >= qs && r <= qe) {
if (tree[rt] <= x) flag = true;
return;
}
int mid = (l + r) >> 1;
query(l, mid, qs, qe, x, lrt[rt]);
query(mid + 1, r, qs, qe, x, rrt[rt]);
}

int main(void) {
int op, x, y1, y2, c;
while (~scanf("%d", &op) && op != 3) {
if (op == 0) clear();
else if (op == 1) {
scanf("%d%d%d", &x, &y1, &c);
update(1, LIM, y1, x, rootPos[c]);
} else if (op == 2) {
scanf("%d%d%d", &x, &y1, &y2);
int ans = 0;
for (int i = 0; i <= 50; i++) {
flag = false;
query(1, LIM, y1, y2, x, rootPos[i]);
if (flag) ans++;
}
printf("%d\n", ans);
}
}
return 0;
}```