PKU 1177 Picture .

The corresponding boundary is the whole set of line segments drawn in Figure 2.

The vertices of all rectangles have integer coordinates.

8927215GZHU10061001061177Accepted1528K110MSC++3841B2011-07-19 11:12:09//Event Sort Begin for (j = i = 0; i < n; i++) { xi[j].x = rec[i].l; xi[j].b = bs(rec[i].b, 0, 2 * n - 1); xi[j].t = bs(rec[i].t, 0, 2 * n - 1); xi[j++].f = 0; xi[j].x = rec[i].r; xi[j].b = xi[j - 1].b; xi[j].t = xi[j - 1].t; xi[j++].f = 1; } sort(xi, xi + n * 2); //Event Sort End?关于线段树解决矩形问题baidu一下大把，有了解既应该知道呢类算法既一种感性理解就系想象有一条竖直扫描线，将矩形班油仔从左向右扫描一次取得一滴统计数据。扫描数组xi其实模拟呢个。注意到记录x坐标上y线段t(top)同埋b(bottom)既时候就用左bs(BinarySearch)用位置等效替代。之后我地就可以直接使用呢滴相对位置鸟。?所以离散化其实系一样好简单既野，就系个名吓人一滴。仲有我觉得叫离散化好似有滴怪，因为距实际操作系压缩坐标 {= =}