## HOJ 12884 Area Coverage（线段树、求矩形面积并）

2019年02月12日 ⁄ 综合 ⁄ 共 1636字 ⁄ 字号 评论关闭

AC代码：

```#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int maxn = 1200;

int len[maxn<<2], cov[maxn<<2];
int xx[maxn<<1];
int xl, yl, xr, yr, xm;
int tmpl, tmpr;

struct segment
{
int xl, xr, y;
int col;
segment(int _xl = 0, int _xr = 0, int _y = 0, int _col = 0):
xl(_xl), xr(_xr), y(_y), col(_col) {}
bool operator < (const segment &argu) const
{
return y < argu.y;
}
}ss[maxn<<1];

void pushup(int l, int r, int rt)
{
if(cov[rt]) len[rt] = xx[r] - xx[l];
else if(l + 1 == r) len[rt] = 0;
else len[rt] = len[rt<<1] + len[rt<<1|1];
}

void update(int L, int R, int add, int l = 0, int r = xm, int rt = 1)
{
if(L <= l && r <= R)
{
pushup(l, r, rt);
return ;
}
int m = (l + r) >> 1;
if(L < m) update(L, R, add, l, m, rt<<1);
if(R > m) update(L, R,add, m, r, rt<<1|1);
pushup(l, r, rt);
}

int bin(int xi)
{
return (lower_bound(xx, xx+xm, xi) - xx);
}

int main()
{
int cas;
scanf("%d", &cas);
while(cas--)
{
int n;
scanf("%d", &n);

memset(cov, 0, sizeof(cov));
memset(len, 0, sizeof(len));

for(int i = 0; i < n; i++)
{
scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
xx[i<<1] = xl;
xx[i<<1|1] = xr;
ss[i<<1] = segment(xl, xr, yl, 1);
ss[i<<1|1] = segment(xl, xr, yr, -1);
}

int set = n << 1;
sort(xx, xx+set);
sort(ss, ss+set);

xm = 0;
for(int i = 1; i < set; i++)
{
if(xx[i] != xx[i-1])
xx[++xm] = xx[i];
}

long long cnt = 0;
set--;
for(int i = 0; i < set; i++)
{
tmpl = bin(ss[i].xl);
tmpr = bin(ss[i].xr);
update(tmpl, tmpr, ss[i].col);
cnt += (long long)len[1] * (long long)(ss[i+1].y-ss[i].y);
}
printf("%I64d\n", cnt);
}
return 0;
}
```