【油漆面积——线段树，扫描线，不用pushdown的特例，pushup兼有cal的性质】

题目

分析

不用pushdown是因为：

对于modify，操作是互逆过程，因此不会存在向下结算的pushdown过程

对于query，操作始终针对最上层的tr[1]，也不需要pushdown

对于pushdown，一则是怕不结算就标记，会通过影响运算顺序，进而影响答案；二则是为了要查没有计算过的深层的帐

代码 #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e4+10; int n, m; struct segment { int x, y1, y2; int k; bool operator < (const segment &b) const { return x < b.x; } } a[2 * N]; struct node { int l, r; int st, len; } tr[4 * N]; void pushup(int u) { if(tr[u].st) tr[u].len = tr[u].r - tr[u].l + 1; else if(tr[u].r == tr[u].l) tr[u].len = 0; else tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len; } void build(int u, int l, int r) { tr[u] = {l, r}; if(l == r) return; else { int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid+1, r); //pushup(u); } } void modify(int u, int l, int r, int k) { if(l <= tr[u].l && tr[u].r <= r) tr[u].st += k; else { int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u << 1, l, r, k); if(r > mid) modify(u << 1 | 1, l, r, k); } pushup(u); //这里放到外面是因为pushup还有cal的作用(通过st计算len)，所以哪怕没有用到左右结点也要调用 } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; a[++m] = {x1, y1, y2, 1}; a[++m] = {x2, y1, y2, -1}; } sort(a+1, a+m+1); build(1, 0, 9999); ll ans = 0; for(int i = 1; i <= m; i++) { if(i > 1) ans += (ll)tr[1].len * (a[i].x - a[i-1].x); modify(1, a[i].y1, a[i].y2 - 1, a[i].k); } cout << ans; }