题解 UVA11983 【Weird Advertisement】
紫题
2019-01-15 22:25:10
### 题意：在坐标系内给出N个矩形，求至少被覆盖k次的面积
扫描线~~毒瘤~~好题
提交20+次才AC，发个题解纪念一下
**前置技能：线段树，扫描线**
先将y坐标离散化，然后对每个矩形$(x0,y0,x1,y1)$，保存为两个四元组
$(x0,y0,y1+1,1)$和$(x1+1,y0,y1+1,-1)$
对所有四元组按照$x$排序后，用扫描线的套路求出当前被覆盖k次的长度$len$，累加答案即可
关于扫描线求矩形面积并的基本用法可以百度板子题**POJ1151 Atlantis**，这里不再赘述
另外，本题只关心根节点的答案，所以线段树可以不用下传延迟标记；
线段树每个节点$(l,r)$保存被覆盖的次数$cnt$,和覆盖$i$次的长度$len[i]$；
每扫描一个四元组$(x,y1,y2,c)$，就将区间$(val(y1),val(y2)-1)$代表的线段树节点都加上$c$，然后从下往上更新$len$即可。另外要注意坐标边界问题。
$Code:$
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct w{
int x, yd, yu, c;
bool operator < (const w &g) const { return x < g.x; }
}q[60010];
struct tree{ int cnt, len[11]; }ak[240010];
int s[60010], n, m, k, t;
inline int val(int x) { return lower_bound(s + 1, s + m + 1, x) - s; }
inline int raw(int x) { return s[x]; }
void build(int p, int l, int r) {
ak[p].cnt = 0;
memset(ak[p].len, 0, sizeof(ak[p].len));
if(l == r) return;
int mid = (l + r) >> 1;
build(p * 2, l, mid); build(p * 2 + 1, mid + 1, r);
}
void update(int p, int l, int r) {
memset(ak[p].len, 0, sizeof(ak[p].len));
for(int i = 0; i <= min(k, ak[p].cnt); i++) ak[p].len[i] = raw(r + 1) - raw(l);
if(l != r) for(int i = 1; ak[p].cnt + i <= k; i++)
ak[p].len[ak[p].cnt + i] = ak[p * 2].len[i] + ak[p * 2 + 1].len[i];
}
void add(int p, int l, int r, int s, int t, int va) {
if(l > t || r < s) return;
if(l >= s && r <= t) {
ak[p].cnt += va; update(p, l, r);
return;
}
int mid = (l + r) >> 1;
add(p * 2, l, mid, s, t, va), add(p * 2 + 1, mid + 1, r, s, t, va);
update(p, l, r);
}
int main() {
scanf("%d", &t);
for(int step = 1; step <= t; step++) {
int aa, bb, cc, dd; long long ans = 0;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &aa, &bb, &cc, &dd);
q[2 * i - 1] = (w){aa, bb, dd + 1, 1}, q[2 * i] = (w){cc + 1, bb, dd + 1, -1};
s[2 * i - 1] = bb, s[2 * i] = dd + 1;
}
sort(q + 1, q + 2 * n + 1);
sort(s + 1, s + 2 * n + 1);
m = unique(s + 1, s + 2 * n + 1) - s - 1;
build(1, 1, m - 1);
for(int i = 1; i <= 2 * n; i++) {
if(i > 1 && q[i].x != q[i - 1].x) ans += 1ll * ak[1].len[k] * (q[i].x - q[i - 1].x);
add(1, 1, m - 1, val(q[i].yd), val(q[i].yu) - 1, q[i].c);
}
printf("Case %d: %lld\n", step, ans);
}
return 0;
}
```