给出n 个矩形，求它们的面积并。 更准确一点，每个矩形将给出它的左上角和右下角的位置：x1; y1; x2; y2 这四个数都是整数且满足x1 x2; y1 y2． Input 第1 行1 个整数：n，表示矩形的个数。 接下来n 行，每行4 个整数：x1 y1 x2 y2，表示一个矩形的左上角和右下角的坐标。 Output 输出area。 Sample area.in 3 1 1 2 3 1 2 3 3 3 3 4 4 area.out 11 样例解释：一共有11 个点落在了上面三个矩形所表示的区域内： (1; 1); (1; 2); (1; 3); (2; 1); (2; 2); (2; 3); (3; 2); (3; 3); (3; 4); (4; 3); (4; 4)
扫描线，对于一个举行(x1,y1,x2,y2)，将它看成两个事件：在x1 这个时间将 (y1,y2) 这个区间加一，在x2+1 这个时间将(y1,y2) 这个区间减一。 这样，我们遍历整个时间，并在执行完这个时间的操作后看看有多少位置非0, 将其数量加到答案中，就完了，当然时间不能傻傻地一个一个枚，因为关键的时间点最多2n 个，其它时候面积是没有变的，所以要一段一段地算。至于怎么用线段树实现那么查看有多少个非零的位置，需要注意对于任何一个减一操作，前面一定有一个和它一样的加一操作，就只需要维护一下每个节点被完全覆盖的次数。再用另一个来统计子树中的那些修改导致这个节点还有 多少个非零。有点像标记永久化
#include "cctype" #include "cstdio" #include "algorithm" const int MAXN = (int) 1e5 + 5; const int Ins = 1, Del = -1; typedef long long LL; template <class T> inline bool readIn(T &x) { T opt = 1; char ch; while( !isdigit(ch = (char) getchar()) && (ch ^ -1) && (ch ^ 45) ); if(ch == -1) return false; if(ch == 45) opt = -1, ungetc(ch, stdin); for(x = ch - 48; isdigit(ch = (char) getchar()); x = (x << 1) + (x << 3) + ch - 48); x *= opt; } struct Events { int type, time, lf, rg; Events(int type = 0, int time = 0, int lf = 0, int rg = 0) : type(type), time(time), lf(lf), rg(rg) { } inline bool operator < (const Events &rhs) const { return time < rhs.time; } } events[MAXN << 1]; struct node { int cnt, sum; node *ls, *rs; node(int cnt = 0, int sum = 0, node *ls = 0, node *rs = 0) : cnt(cnt), sum(sum), ls(ls), rs(rs) { } inline int query(int lf, int rg) { return cnt ? rg - lf + 1 : sum; } inline void update(int lf, int rg) { int mid = (lf + rg) >> 1; sum = ls -> query(lf, mid) + rs -> query(mid + 1, rg); } } pool[MAXN << 1], *root, *tail = pool; int n, x1, y1, x2, y2, tot; LL ans; node *build(int lf, int rg) { node *nd = ++tail; if( lf == rg ) return nd; int mid = (lf + rg) >> 1; nd -> ls = build(lf, mid); nd -> rs = build(mid + 1, rg); // alredy initialized; return nd; } void modify(node* &nd, int lf, int rg, int L, int R, int delta) { if(L > lf || R < rg) { int mid = (lf + rg) >> 1; if(L <= mid) modify(nd -> ls, lf, mid, L, R, delta); if(R > mid) modify(nd -> rs, mid + 1, rg, L, R, delta); nd -> update(lf, rg); } else nd -> cnt += delta; return; } int main() { freopen("area.in", "r", stdin); freopen("area.out", "w", stdout); readIn(n); for(register int i = 1; i <= n; ++i) { readIn(x1), readIn(y1), readIn(x2), readIn(y2); events[tot++] = Events(1, x1, y1, y2); events[tot++] = Events(-1, x2 + 1, y1, y2); } std::sort(events, events + tot); root = build(1, MAXN); for(register int i = 0, j; i < tot; i = j + 1) { for(j = i; j < tot && events[j + 1].time == events[i].time; ++j); for(register int k = i; k <= j; ++k) modify(root, 1, MAXN, events[k].lf, events[k].rg, events[k].type); if(j ^ (tot - 1)) ans += (LL) root -> query(1, MAXN) * (events[j + 1].time - events[i].time); } printf("%lld\n", ans); return 0; }