卡这题卡了一天左右，不会做额，找了不少的代码和解说，发现NOCOW这里很不错，有大牛在这里写方法，可以拓宽思路，这几个1,2,3还不错，看懂了，和HDU1543是同一道题，就说说题意和方法吧。
给定一个A*B的矩形，A<10^4,B<10^4，然后可以往这个矩形上涂矩形状的颜色，矩形和X，Y轴平行，如果涂到同一个地方，则覆盖原来的颜色，颜色C<2500，有N<1000个矩形，求最后剩下的各个颜色的个数。
有很多方法了，矩形分割，线段树，并查集优化，等等，但调了线段树来看，顺便复习下线段树。用二维实现的话，空间很紧，于是就牺牲时间换空间，用一维的线段树来实现，离散化然后扫描线。我将矩形的x方向的值离散化掉，然后扫描从左到右，对于每两个线x1,x2，先创建一颗线段树，按读入顺序遍历矩形，判断是否覆盖x1,x2，如果覆盖，则该矩形对该区间覆盖有效，则将该Y方向上的线段插入线段树中，之后，统计树上的颜色值。
想到的有两个细节：
1. 遍历矩形的顺序可以按实现的方法来选择，反过来的话，即涂过的地方就不涂了.
2. 原先的矩形都是颜色1，可以事后再统计.
这样子就可以通过USACO上的题了，注意在线段树上涂色的方法实现，详情见代码中加*处，线段树的原理之一就是基于子树就是当前数的子集划分，由它代替所有子树，如果没必要时，在当前树这儿就可以停止了，但如果继续深入的话，要注意子树的数据是否是更新的，如果不是更新的，要注意更新。下面的代码在第11组数据处花了1.7+s时间，可以把Y方向和颜色C都离散化掉，应该会快的，就没改了。
接下来把矩形分割的方法学一下，线段树+离散化+扫描线的代码如下：
/* ID: litstrong PROG: rect1 LANG: C++ */ #include <iostream> #include <string> #include <vector> #include <set> #include <math.h> #include <queue> #include <algorithm> #include <string.h> #include <stdio.h> using namespace std; const int MAXN = 10005; const int MAXC = 2505; int c_cnt[MAXC]; int c_ans[MAXC]; int x_line[MAXN * 2]; class CSEG { public: int L, R, C; //C表示颜色 public: CSEG() {} CSEG(int _L, int _R, int _C) : L(_L), R(_R), C(_C) {} }; //区间树，线段树的变形 class CSEGTREE { public: CSEG segs[MAXN * 5]; public: void Build(int root, int L, int R) { segs[root] = CSEG(L, R, 1); int M = (L + R) / 2; //printf("%d %d %d\n", root, L, R); if(R - L > 1) //非叶子的话扩展 { if(L < M) Build(2 * root, L, M); if(M < R) Build(2 * root + 1, M, R); } } void Insert(int root, int line_L, int line_R, int C) { //segs[root].L <= segs[root].R //printf("%d %d %d %d %d\n", root, segs[root].L, segs[root].R, line_L, line_R); if(line_L <= segs[root].L && line_R >= segs[root].R) //完全覆盖 { segs[root].C = C; //下面的不更新了，之后再更新 return; } if(segs[root].C != -1) { if(segs[root].C == C) return; //剪枝 //否则扩展，记住这时往下更新 segs[2 * root].C = segs[2 * root + 1].C = segs[root].C; //****** } segs[root].C = -1; //部分覆盖，标记为混色，用于查询时的优化 int M = (segs[root].L + segs[root].R) / 2; if(line_R > M) Insert(2 * root + 1, line_L, line_R, C); if(line_L < M) Insert(2 * root, line_L, line_R, C); } void Query(int root) { if(segs[root].C != -1) { c_cnt[segs[root].C] += (segs[root].R - segs[root].L); return; } Query(2 * root); Query(2 * root + 1); } }; class CRECT { public: int nx, mx, ny, my, c; public: CRECT() {} CRECT(int _nx, int _mx, int _ny, int _my, int _c) : nx(_nx), mx(_mx), ny(_ny), my(_my), c(_c) {} }rect[MAXN]; int main() { freopen("rect1.in", "r", stdin); freopen("rect1.out", "w", stdout); int A, B, N; scanf("%d%d%d", &A, &B, &N); for(int i = 0; i < N; i++) { int nx, mx, ny, my, c; scanf("%d%d%d%d%d", &nx, &ny, &mx, &my, &c); rect[i] = CRECT(min(nx, mx), max(nx, mx), min(ny, my), max(ny, my), c); x_line[2 * i] = nx; x_line[2 * i + 1] = mx; } sort(x_line, x_line + 2 * N); memset(c_ans, 0, sizeof(c_ans)); CSEGTREE tree; for(int i = 1; i < 2 * N; i++) { if(x_line[i - 1] == x_line[i]) continue; tree.Build(1, 0, B); //printf("Build ok\n"); memset(c_cnt, 0, sizeof(c_cnt)); for(int j = 0; j < N; j++) { if(rect[j].nx <= x_line[i - 1] && rect[j].mx >= x_line[i]) { tree.Insert(1, rect[j].ny, rect[j].my, rect[j].c); //printf("Insert ok\n"); } } tree.Query(1); for(int j = 0; j < MAXC; j++) { c_ans[j] += c_cnt[j] * (x_line[i] - x_line[i - 1]); } //printf("#%d, %d, %d*%d=%d\n", c_cnt[1], c_cnt[3], c_cnt[2], (x_line[i] - x_line[i - 1]), c_cnt[2] * (x_line[i] - x_line[i - 1])); } c_ans[1] += (A - x_line[2 * N - 1] + x_line[0]) * B; for(int i = 0; i < MAXC; i++) { if(c_ans[i]) printf("%d %d\n", i, c_ans[i]); } }转载于:https://www.cnblogs.com/litstrong/archive/2011/03/04/1971189.html
相关资源：数据结构—成绩单生成器