【油漆面积——线段树，扫描线，不用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;
}