题意很简单,即求矩形面积并。
看了zkw版线段树,感觉那种建树的方法不适合我0.0
我的树的区间表示为[l, r),所以pushup函数里面是if(l + 1 == r) len[rt] = 0;
然后为了求快,没有建树,直接memset了。
详细说我对扫描线-线段树的理解吧。
来一条矩形的下边,则表示在以上区域都是有面积的,于是给有面积的区间染色一次;下边表示减去它所属的矩形下边给该区域的影响。
在区间上+1和-1相当于给区间染色,+1是加重颜色,-1是减弱。如果该区间有颜色,那么这个区间的长度就应该是它的右x值减去左x值;如果没有颜色,再判断是否是叶子节点,叶子节点的长度赋为0(因为没有染色);如果不是叶子节点,那么这个区间不是没有任何染色,就是染色是分开的。
AC代码:
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn = 1200; int len[maxn<<2], cov[maxn<<2]; int xx[maxn<<1]; int xl, yl, xr, yr, xm; int tmpl, tmpr; struct segment { int xl, xr, y; int col; segment(int _xl = 0, int _xr = 0, int _y = 0, int _col = 0): xl(_xl), xr(_xr), y(_y), col(_col) {} bool operator < (const segment &argu) const { return y < argu.y; } }ss[maxn<<1]; void pushup(int l, int r, int rt) { if(cov[rt]) len[rt] = xx[r] - xx[l]; else if(l + 1 == r) len[rt] = 0; else len[rt] = len[rt<<1] + len[rt<<1|1]; } void update(int L, int R, int add, int l = 0, int r = xm, int rt = 1) { if(L <= l && r <= R) { cov[rt] += add; pushup(l, r, rt); return ; } int m = (l + r) >> 1; if(L < m) update(L, R, add, l, m, rt<<1); if(R > m) update(L, R,add, m, r, rt<<1|1); pushup(l, r, rt); } int bin(int xi) { return (lower_bound(xx, xx+xm, xi) - xx); } int main() { int cas; scanf("%d", &cas); while(cas--) { int n; scanf("%d", &n); memset(cov, 0, sizeof(cov)); memset(len, 0, sizeof(len)); for(int i = 0; i < n; i++) { scanf("%d%d%d%d", &xl, &yl, &xr, &yr); xx[i<<1] = xl; xx[i<<1|1] = xr; ss[i<<1] = segment(xl, xr, yl, 1); ss[i<<1|1] = segment(xl, xr, yr, -1); } int set = n << 1; sort(xx, xx+set); sort(ss, ss+set); xm = 0; for(int i = 1; i < set; i++) { if(xx[i] != xx[i-1]) xx[++xm] = xx[i]; } long long cnt = 0; set--; for(int i = 0; i < set; i++) { tmpl = bin(ss[i].xl); tmpr = bin(ss[i].xr); update(tmpl, tmpr, ss[i].col); cnt += (long long)len[1] * (long long)(ss[i+1].y-ss[i].y); } printf("%I64d\n", cnt); } return 0; }