题目太长了就直接放链接吧
http://acm.hdu.edu.cn/showproblem.php?pid=6183
题意：
一个空的坐标系，有④种操作：①1 x y c表示在(x, y)点染上颜色c；②2 X y1 y2表示查询在(1, y1)到(X, y2)范围内有多少种不同的颜色：③0表示清屏；④3表示程序退出（0<=x, y<=1000000, 0<=c<=50）
主要就是前两个操作，后面两个操作其实就是多实例的意思
直接线段树就好了
颜色只有50种，可以建50棵线段树然后暴力
对于每一种颜色，因为查询的横坐标是1到X，所以对于每个y，你只需要知道离y轴最近的那个点在哪里
这样的话就可以按y坐标建树，查询的时候判断下范围内有没有点即可
这题有点卡常数，要优化下
#include<stdio.h> #include<string.h> int c, d, X, ok, root[55]; int cnt, L[3300000], R[3300000], v[3300000]; void Update(int &k, int l, int r, int a, int b) { int m; if(k==0) { k = ++cnt; v[k] = b; } if(v[k]>b) v[k] = b; if(l==r) return; m = (l+r)/2; if(a<=m) Update(L[k], l, m, a, b); else Update(R[k], m+1, r, a, b); } void Query(int x, int l, int r) { int m; if(ok || x==0) return; if(l>=c && r<=d) { if(v[x]<=X) ok = 1; return; } m = (l+r)/2; if(c<=m) Query(L[x], l, m); if(d>=m+1) Query(R[x], m+1, r); } int main(void) { int i, ans, opt, x, y; while(1) { scanf("%d", &opt); if(opt==3) break; else if(opt==0) { for(i=1;i<=cnt;i++) L[i] = R[i] = 0; memset(root, 0, sizeof(root)); cnt = 0; } else if(opt==1) { scanf("%d%d%d", &x, &y, &c); Update(root[c], 1, 1000000, y, x); } else if(opt==2) { scanf("%d%d%d", &X, &c, &d); ans = 0; for(i=0;i<=50;i++) { ok = 0; Query(root[i], 1, 1000000); ans += ok; } printf("%d\n", ans); } } return 0; }
