【洛谷】P1856

[IOI1998] 矩形周长Picture

#线段树 #数据结构

题目背景

墙上贴着许多形状相同的海报、照片。它们的边都是水平和垂直的。每个矩形图片可能部分或全部的覆盖了其他图片。所有矩形合并后的边长称为周长。

题目描述

编写一个程序计算周长。

如图 $1$ 所示 $7$ 个矩形。

如图 $2$ 所示，所有矩形的边界。所有矩形顶点的坐标都是整数。

输入格式

输入文件的第一行是一个整数 $N$，表示有多少个矩形。接下来 $N$ 行给出了每一个矩形左下角坐标和右上角坐标。

输出格式

输出文件只有一个正整数，表示所有矩形的周长。

样例 #1

样例输入 #1

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

样例输出 #1

228

提示

数据范围及约定

对于全部数据，$1\le N<5000$，所有坐标的数值范围都在 $-10^4$ 到 $10^4$ 之间。

思路

首先长度一定当前线段树维护的长度与上一次的距离，宽度就是两条扫描线之间的距离，但是需要判断有几条，也就是有几个并起来的块。

我们需要在原先的扫描线上添加一个左右覆盖的标记$lcover$和$rcover$，以及条数$sum$。

答案就是 ${\sum }_{i=1}^{i\le n}(le{n}_i-le{n}_{i-1}))\ast 2+sum\ast abs(L_i-L_{i-1})$

代码

const int N = 1e5 + 10;struct line {int x1, x2, y;int tag; // 1/0 入边出边bool operator<(const line& l) const {return y < l.y;}
}L[N];#define ls(x) x<< 1 
#define rs(x) x<< 1 | 1  struct node {int l, r, cnt, len, sum, lcover, rcover;
}tree[N * 8];int X[N];void build(int p, int l, int r) {tree[p] = { l,r,0,0,0,0 };if (l == r) {return;}int mid = l + r >> 1;build(ls(p), l, mid);build(rs(p), mid + 1, r);
}void push_up(int p) {int l = tree[p].l, r = tree[p].r;if (tree[p].cnt) {tree[p].len = X[r + 1] - X[l];tree[p].sum = 2;tree[p].lcover = tree[p].rcover = 1;}else {tree[p].len = tree[ls(p)].len + tree[rs(p)].len;tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;tree[p].lcover = tree[ls(p)].lcover;tree[p].rcover = tree[rs(p)].rcover;if (tree[ls(p)].rcover && tree[rs(p)].lcover) {tree[p].sum -= 2;}}
}void update(int p, int x, int y, int tag) {if (x <= tree[p].l && y >= tree[p].r) {tree[p].cnt += tag;push_up(p);return;}int mid = tree[p].l + tree[p].r >> 1;if (y <= mid) {update(ls(p), x, y, tag);}else if (x >= mid + 1) {update(rs(p), x, y, tag);}else {update(ls(p), x, y, tag);update(rs(p), x, y, tag);}push_up(p);
}void solve() {int n;std::cin >> n;for (int i = 1; i <= n; ++i) {int x1, y1, x2, y2;std::cin >> x1 >> y1 >> x2 >> y2;X[i] = x1; X[i + n] = x2;L[i] = { x1,x2,y1,1 }; L[i + n] = { x1,x2,y2,-1 };}n <<= 1;std::sort(X + 1, X + 1 + n);std::sort(L + 1, L + 1 + n);int m = std::unique(X + 1, X + 1 + n) - X - 1;build(1, 1, m - 1);ll res = 0, last = 0;for (int i = 1; i <= n - 1; ++i) {int l = std::lower_bound(X + 1, X + m + 1, L[i].x1) - X;int r = std::lower_bound(X + 1, X + m + 1, L[i].x2) - X;update(1, l, r - 1, L[i].tag);res += std::abs(tree[1].len - last);res += (ll)tree[1].sum * (ll)(L[i + 1].y - L[i].y);last = tree[1].len;}res += L[n].x2 - L[n].x1;std::cout << res << "\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}return 0;
}