HDU 1828：Picture（扫描线+线段树 矩形周长并）题意思路

题目链接

题意

给出n个矩形，求周长并。

思路

学了区间并，比较容易想到周长并。

我是对x方向和y方向分别做两次扫描线。应该记录一个pre变量，记录上一次扫描的时候的长度，对于每次遇到扫描线统计答案的时候，使用当前的 tree[1] 去与 pre 做相减，因为这一次如果边长增加了或者减少了，那么一定和之前的值有差值，其中的差值就是这次的变化量。

但是这份代码交G++会WA，C++就A了。而且排序的时候如果权值相同，应该让状态为1（开始）的扫描线排在状态为-1（结束）的扫描线前面，因为重合的话，那个边长不可计算到答案里面的。如果先更新结束的，代表这一段边长（如果更新之后消失了的话）会导致算上这一部分的贡献，然后又更新开始的，又算上一次这一部分的贡献，等于算上了两次。然而真实情况下，是不应该算上这部分的贡献的。

这题不用离散化也可以，习惯性。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e4 + 10;
#define lson l, m, rt<<1
#define rson m + 1, r, rt<<1|1
typedef long long LL;
struct Node {
int l, r, w, st;
Node () {}
Node (int _l, int _r, int _w, int _st) {
l = _l, r = _r, w = _w, st = _st;
}
bool operator < (const Node &rhs) const {
if(w == rhs.w) return st > rhs.st; // 开始在结束前面
return w < rhs.w;
}
} px[N], py[N];
int tree[N<<2], cnt[N<<2];
int x[N], y[N];
void pushup(int l, int r, int rt, int *axis) {
if(cnt[rt] > 0) tree[rt] = axis[r+1] - axis[l];
else if(l == r) tree[rt] = 0;
else tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void update(int L, int R, int w, int l, int r, int rt, int *axis) {
if(L <= l && r <= R) {
cnt[rt] += w;
pushup(l, r, rt, axis);
return ;
}
int m = (l + r) >> 1;
if(L <= m) update(L, R, w, lson, axis);
if(m < R) update(L, R, w, rson, axis);
pushup(l, r, rt, axis);
}
int solve(int n, int *axis, Node *p, int ct) {
memset(tree, 0, sizeof(tree));
memset(cnt, 0, sizeof(cnt));
int ans = 0, pre = 0;
for(int i = 1; i <= n; i++) {
int L = lower_bound(axis + 1, axis + 1 + ct, p[i].l) - axis;
int R = lower_bound(axis + 1, axis + 1 + ct, p[i].r) - axis - 1;
update(L, R, p[i].st, 1, ct, 1, axis);
ans += abs(tree[1] - pre);
pre = tree[1];
}
return ans;
}
int main() {
int n;
while(~scanf("%d", &n)) {
int cntx = 0, cnty = 0;
for(int i = 1; i <= n; i++) {
int x1, x2, y1, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
x[++cntx] = x1; x[++cntx] = x2;
y[++cnty] = y1; y[++cnty] = y2;
px[i*2-1] = Node(y1, y2, x1, 1);
px[i*2] = Node(y1, y2, x2, -1);
py[i*2-1] = Node(x1, x2, y1, 1);
py[i*2] = Node(x1, x2, y2, -1);
}
sort(x + 1, x + 1 + cntx);
sort(y + 1, y + 1 + cnty);
cntx = unique(x + 1, x + 1 + cntx) - x - 1;
cnty = unique(y + 1, y + 1 + cnty) - y - 1;
int m = 2 * n;
sort(px + 1, px + 1 + m);
sort(py + 1, py + 1 + m);
int ans = solve(m, x, py, cntx) + solve(m, y, px, cnty);
printf("%dn", ans);
}
return 0;
}
/*
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
*/