洛谷P5490扫描线

2024-09-05 20:28
文章标签 洛谷 扫描线 p5490

本文主要是介绍洛谷P5490扫描线,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1)

那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去0的个数是不是就是现在线段所覆盖过的长度?

对于1e9的数据范围,我们首先需要离散化,例如题中给的样例将所有的x坐标拿出来排序100,150,200,250.离散化以后得到0,1,2,3.我们将这个离散化映射表用map表示map[0]=100,map[1]=150......

建立一个总长为3的线段树,那么节点[0,1)看做是线段[0,1],节点[1,2)看做线段[1,2]以此类推.

那么一个节点需要记录以下信息

0和0的长度->mn,cnt

考虑使用单点修改初始化,将[0,1)节点的cnt初始化为map[1]-map[0].

记得初始化高度为第一条线段的高度,首先查询0的个数,然后计算答案(第一次不起任何作用)=(高度*(总长-0的个数))=(Line[i].h-h)*(map[k-1]-map[0]-rangeQuery(0,k-1).cnt),然后区间修改,将该区间所有数+1,rangeApply(Line[i].l,Line[i].r,{Line[i].tag});

最终就可以得出答案了.

下面列举出来的线段树板子会执行懒标记线段树的功能,你只需要将节点信息Info,懒标记Tag,和+operator写好就行.

我使用的离散化思路是排序,去重二分查找,map作为一个映射表,二分查找的目的是为了将Line[i]中记录的左右端点换成映射值.

using ll = long long;
using i64 = long long;
template<class Info, class Tag>
struct LazySegmentTree {int n;std::vector<Info> info;std::vector<Tag> tag;LazySegmentTree() : n(0) {}LazySegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>LazySegmentTree(std::vector<T> init_) {init(init_);}void init(int n_, Info v_ = Info()) {init(std::vector<Info>(n_, v_));}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << (int)std::log2(n), Info());tag.assign(4 << (int)std::log2(n), Tag());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void apply(int p, const Tag& v) {info[p].apply(v);tag[p].apply(v);}void push(int p) {apply(2 * p, tag[p]);apply(2 * p + 1, tag[p]);tag[p] = Tag();}void modify(int p, int l, int r, int x, const Info& v) {if (r - l == 1) {info[p] = v;return;}int m = (l + r) / 2;push(p);if (x < m) {modify(2 * p, l, m, x, v);}else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info& v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;push(p);return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}void rangeApply(int p, int l, int r, int x, int y, const Tag& v) {if (l >= y || r <= x) {return;}if (l >= x && r <= y) {apply(p, v);return;}int m = (l + r) / 2;push(p);rangeApply(2 * p, l, m, x, y, v);rangeApply(2 * p + 1, m, r, x, y, v);pull(p);}void rangeApply(int l, int r, const Tag& v) {return rangeApply(1, 0, n, l, r, v);}};
struct Line {ll l, r, h, tag;
};
struct Tag
{i64 p;void apply(const Tag& t) { p += t.p; }
};
struct Info
{i64 mn,cnt = 0;void apply(const Tag& t) {mn += t.p; }
};
Info operator+(const Info &a,const Info& b)
{Info res = { std::min(a.mn, b.mn), 0 };if (a.mn == res.mn) res.cnt += a.cnt;if (b.mn == res.mn) res.cnt += b.cnt;return res;
}void solve() {int n;std::cin >> n;std::vector<Line> line(2 * n);std::vector<ll> map(2 * n);for (int i = 0; i < n; i++) {ll x1, y1, x2, y2;std::cin >> x1 >> y1 >> x2 >> y2;line[i] = { x1, x2, y1, 1 };  // 下边,权值为1line[i + n] = { x1, x2, y2, -1 };  // 上边,权值为-1map[i] = x1;map[i + n] = x2;}std::sort(line.begin(), line.end(), [&](Line x, Line y) {return x.h < y.h;});std::sort(map.begin(), map.end());for (int i = 2 * n - 1; i > 0; i--) {if (map[i] == map[i - 1])map.erase(map.begin() + i);}auto search = [&](int l, int r, int x) {while (l + 1 < r) {int mid = (l + r) / 2;if (map[mid] > x)r = mid;else l = mid;}return l;};int k = map.size();for (int i = 0; i < 2 * n; i++) {line[i].l = search(-1, k, line[i].l);line[i].r = search(-1, k, line[i].r);}LazySegmentTree<Info, Tag> tree(k);for (int i = 0; i < k - 1; i++) {tree.modify(i,{0, map[i+1] - map[i] });}//0,1,2,3ll ans = 0, h = line[0].h;for (int i = 0; i < 2 * n; i++) {Info res = tree.rangeQuery(0, k-1);if (res.mn == 0) {ans += (line[i].h - h) * (map[k-1] - res.cnt-map[0]);}h = line[i].h;tree.rangeApply(line[i].l, line[i].r, { line[i].tag });  // 更新区间}std::cout << ans << "\n";
}
int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t=1;//std::cin >> t;while (t--) {solve();}return 0;
}

这篇关于洛谷P5490扫描线的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139977

相关文章

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

Zxing扫描二维码精简(竖屏、拉伸处理、扫描框大小和扫描线移动、开灯)

自己在简版zxing的基础上美化了下,给大家分享下,直接扫描功能没问题。 就是从相册导入图片,解码一直不成功,导入图片解码 我引入了一个解码类  RGBLuminanceSource(百度网上二维码图片解码都是这个,我还把这个类编译了,导到core.jar包里面了), 好像是hity类型有问题,反正一直不成功。 有大神解决了,回复告诉我!谢谢! 分享 暂时没做效

挤牛奶洛谷uasco

题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

扫描线Sweep Line算法总结

扫描线算法,推荐还是用标准的模板去写,treemap只适合于求最大的overlap个数的题目,其余的不能用treemap来解,所以推荐还是用event的思想去+1, -1然后排序扫描的方法可以用来解所有的题型; Number of Airplanes in the Sky 思路:经典扫描线算法:把interval起飞和降落做为event,全部打散,按照时间排列,同时时间相等的,按照降落在前面,起

洛谷刷题(7)

P8738 [蓝桥杯 2020 国 C] 天干地支 题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个,分别为:甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊 (wù)、己(jǐ)、庚(gēng)、辛(xīn)、壬(rén)、癸(guǐ)。 地支一共有十二个,分别为:子(zǐ)、丑(chǒu)、寅(yín)、卯(mǎo)、辰(chén)、巳(sì)、午(wǔ)、

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)

转自:http://blog.csdn.net/lwt36/article/details/48908031 HDU 1542 [POJ 1151] Atlantis (矩形面积并) 题意: 求N<=100个矩形的面积并 分析: 离散化: 这些技巧都是老生常谈的了, 不然浮点数怎么建树, 离散化 x 坐标就可以了扫描线: 首先把矩形按 y 轴分成两条边, 上边和下边,

C++ 洛谷 哈希表(对应题库:哈希,hash)习题集及代码

马上就开学了,又一个卷季,不写点东西怎么行呢?辣么,我不准备写那些dalao们都懂得,熟练的,想来想去,最终还是写哈希表吧!提供讲解&题目&代码解析哦! 奉上题目链接: 洛谷题目 - 哈希,hash 1、哈希、哈希表(hash)简介 哈希(Hash)是一种将任意长度的输入映射为固定长度输出的算法。哈希函数的输出值称为哈希值或散列值。哈希函数具有以下特性: 确定性:对于相同的输入

【HDU1255】【线段树】【扫描线】【面积】

覆盖的面积 Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4417    Accepted Submission(s): 2180 Problem Description 给定平面上若干矩形,求出被这些矩形覆