传送门：HDU6183
题意：有四种操作：
0：把所有点清空
1：在（x，y）上添加一个颜色为 c 的点（不会覆盖以前的颜色）
2：查询横坐标1 到 x1，纵坐标 y1 到 y2 这块区域内颜色种数
3：退出
思路：因为只有51种颜色，建立51颗线段树，每颗线段树节点下标对应颜色c的y坐标值，节点的值为该y坐标下最早出现颜色c的x坐标，因为每次询问都是[1， x1], 易证这样维护是正确的。
由于空间无法满足直接建立50颗线段树的要求，因此要采用动态分配节点的方式。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2000010;
const int N = 1000000;
int rt[51], lson[MAXN], rson[MAXN], val[MAXN];
int tid;
void update(int &rt, int l, int r, int x, int id)
{
if(rt == -1){
rt = ++tid;
lson[rt] = -1;
rson[rt] = -1;
val[rt] = x;
}
val[rt] = min(val[rt], x);
if(l == r) return ;
int mid = (l + r) >> 1;
if(id <= mid)
update(lson[rt], l, mid, x, id);
else
update(rson[rt], mid + 1, r, x, id);
}
bool query(int rt, int l, int r, int L, int R, int x)
{
if(rt == -1) return 0;
if(L <= l && r <= R)
return val[rt] <= x;
int mid = (l + r) >> 1, ans = 0;
if(L <= mid) ans |= query(lson[rt], l, mid, L, R, x);
if(ans) return ans;
if(R > mid) ans |= query(rson[rt], mid + 1, r, L, R, x);
return ans;
}
int main()
{
int tp, x, y, c, y1, y2;
memset(rt, -1, sizeof rt);
while(~scanf("%d", &tp))
{
if(tp == 3) break;
else if(tp == 0){
tid = 0;
memset(rt, -1, sizeof(rt));
}
else if(tp == 1){
scanf("%d %d %d", &x, &y, &c);
update(rt[c], 1, N, x, y);
}
else{
scanf("%d %d %d", &x, &y1, &y2);
int ans = 0;
if(y1 > y2) swap(y1, y2);
for(int i = 0; i <= 50; i++)
ans += query(rt[i], 1, N, y1, y2, x);
printf("%d\n", ans);
}
}
}