线扫描法之周长并

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
/*代码来自大佬*/
typedef long long ll;
const int kMax = 50000 + 10;
struct P {
int x, p, v;//坐标，序号,+1或-1
P(int _x = 0, int _p = 0, int _v = 0) : x(_x), p(_p), v(_v) {}
bool operator < (const P& t) const {//重载<号
return x < t.x;
}
};
struct node {
int l, r, times;//覆盖次数
ll sum, add;//长度，延迟标记
} tree[kMax << 3];
int n;
int num[kMax][4];//坐标
int old[kMax * 2];//辅助，去重离散化
P pos[kMax * 2];//辅助，分离x和y
map<int, int> table;
void pushup(int p) {
tree[p].times = min(tree[p << 1].times, tree[p << 1 | 1].times);//覆盖次数，全是1才是1
}
void pushdown(int p) {//下压覆盖次数
if(tree[p].add) {
tree[p << 1].times += tree[p].add;
tree[p << 1 | 1].times += tree[p].add;
tree[p << 1].add += tree[p].add;
tree[p << 1 | 1].add += tree[p].add;
tree[p].add = 0;
}
}
void build(int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
tree[p].sum = old[tree[p].r] - old[tree[p].l - 1];//坐标上的实际长度,old下标从0开始，所以-1
tree[p].times = 0;
tree[p].add = 0;
if(l == r) return;
int m = (l + r) >> 1;
build(p << 1, l, m);
build(p << 1 | 1, m + 1, r);
}
void update(int p, int l, int r, int val) {//更新
if(l <= tree[p].l && r >= tree[p].r) {
tree[p].times += val;
tree[p].add += val;
return;
}
int m = (tree[p].l + tree[p].r) >> 1;
pushdown(p);
if(l <= m) update(p << 1, l, r, val);
if(r > m) update(p << 1 | 1, l, r, val);
pushup(p);
}
ll query(int p) {
if(tree[p].times) return tree[p].sum;//如果覆盖次数不为0，返回该段长度
if(tree[p].l == tree[p].r) return 0;
pushdown(p);
return query(p << 1) + query(p << 1 | 1);//返回左右子树长度
}
ll myabs(ll a) {
return a > 0 ? a : -a;
}
int main() {
ll res = 0;
scanf("%d", &n);
for(int i = 0;i < n;++ i) {
for(int j = 0;j < 4;++ j)
scanf("%d", &num[i][j]);//存放坐标
}
for(int cd = 0;cd < 2;++ cd) {//分离x，y
int len = 0;
for(int i = 0;i < n;++ i) {//逐个分离
pos[len] = {num[i][(cd + 1) % 2], i, 1};//左下角,y1,x1
old[len ++] = num[i][cd + 0];//x1,y1
pos[len] = {num[i][(cd + 1) % 2 + 2], i, -1};//右上角,y2,x2
old[len ++] = num[i][cd + 2];//x2,y2
}
sort(pos, pos + len);
sort(old, old + len);
len = unique(old, old + len) - old;//去重
for(int i = 0;i < len;++ i) {//离散化
table[old[i]] = i + 1;
}
build(1, 1, len);//建树
ll cur = 0, last = 0;
for(int i = 0;i < n * 2;++ i) {
update(1,
table[num[pos[i].p][cd + 0]], //x1,y1
table[num[pos[i].p][cd + 2]]-1, //x2,y2,一点代表一个区域，1代表坐标上1-2这块区域，所以减一。
pos[i].v);//x1,y1则加1，x2,y2则减1
cur = query(1);//查询当前总长度
res += myabs(cur - last);//结果加上 长度变化的绝对值
last = cur;//上一次的长度
}
}
printf("%lldn", res);
return 0;
}

最后

以上就是聪慧咖啡为你收集整理的线扫描法之周长并的全部内容，希望文章能够帮你解决线扫描法之周长并所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。