;sum[MAX << 2];int col[MAX << 2];//num表示的是这个区间有多少个矩形的两条高要算int num[MAX << 2];//以下的两个变量分别表示区间的左右两边是否被这个矩形所覆盖。bool lb[MAX << 2];bool rb[MAX << 2];int x[MAX << 2];struct seg{int l, r, h;int s;seg(){}seg(int _l, int _r, int _h, int _s){l = _l;r = _r;h = _h;s = _s;}}ss[MAX<<2];bool cmp(seg a, seg b){return a.h < b.h;}void uprt(int l, int r, int rt){if (col[rt]){lb[rt] = rb[rt] = num[rt] = 1;sum[rt] = x[r + 1] – x[l];return;}if (l == r){lb[rt] = rb[rt] = num[rt] = sum[rt] = 0;return;}sum[rt] = sum[rs] + sum[ls];num[rt] = num[rs] + num[ls];lb[rt] = lb[ls];rb[rt] = rb[rs];/*这个需要好好注意哦！假如左边区间的最右边被覆盖，并且右边区间的最左边被覆盖，，那么就意味着这两条是不能算的，所以要减掉1.其实这边的思路是将左区间和右区间先看成两个矩形，假如公共部分被覆盖，则需要减掉两条边*/if (lb[rs] && rb[ls]) num[rt]–;}void updata(int L, int R, int s,int l, int r, int rt){if (L <= l&&r <= R){col[rt] += s;uprt(l, r, rt);return;}int mid = m;if (L <= mid)updata(lson);if (mid < R)updata(rson);uprt(l, r, rt);}int main(){int n;while (cin >> n){int x1, x2, y1, y2;int cnt = 0;for (int i = 0; i < n; i++){scanf(“%d%d%d%d”, &x1, &y1, &x2, &y2);x[cnt] = x1;ss[cnt++] = seg(x1, x2, y1, 1);x[cnt] = x2;ss[cnt++] = seg(x1, x2, y2, -1);}sort(x, x + cnt);sort(ss, ss + cnt, cmp);int cnt2 = unique(x, x + cnt) – x;memset(col, 0, sizeof(col));memset(num, 0, sizeof(num));memset(sum, 0, sizeof(sum));memset(lb, 0, sizeof(lb));memset(rb, 0, sizeof(rb));int pre = 0;int ans = 0;for (int i = 0; i < cnt; i++){int l = lower_bound(x, x + cnt2, ss[i].l) – x;int r = lower_bound(x, x + cnt2, ss[i].r) – x – 1;updata(l, r, ss[i].s, 0, cnt2-1, 1);ans += abs(sum[1] – pre);ans += 2 * num[1] * (ss[i + 1].h – ss[i].h);pre = sum[1];}cout << ans << endl;}}
世上最累人的事，莫过於虚伪的过日子
