扫描线思想
扫描线思想
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135063
https://www.luogu.com.cn/problem/P5490
本质就是把每个矩形拆成上边和下边，下边为加，上边为减（从下往上枚举）
变成处理一维上的线段长度并，拿个线段树维护
最好拿点离散化一下，动态开点容易被制裁
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-24
μ^2的根号暴力计算方法
μ^2的根号暴力计算方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132386010 上结论： 左边式子的本质就是 nnn 以内有多少个数没有平方因子 然后我们枚举所有平方因子 i2i^2i2 ，包含它的有 ni2\Large\frac {n}{i^2}i2n 个 右边本质是一个容斥，首先所有数都有平方因子 121^212 ，然后类似 22,322^2,3^222,32 这类要减掉，有些重复减的要加上，例如 626^262 。而像 42,924^2...
2021-11-17
【P2338 [USACO14JAN]Bessie Slows Down S】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569706.html 题目链接 纯模拟题，无任何算法或思维难度。 难度虚高了。 对于时间和空间分别排个序，然后依次进行就行了。 看一下是先遇到减速地点还是减速时间。 要注意精度问题。 时间复杂度：O(n)O(n)O(n)。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575...
2023-08-10
点分治过程中维护李超线段树：CF1303G
点分治过程中维护李超线段树：CF1303G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132219909 https://www.luogu.com.cn/problem/CF1303G 看到这题，首先很容易想到树形dp，但发现要维护两个值，一个为末项，一个为和，很好分析出这个东西有凸性。 这个时候有两种做法，维护凸包或李超线段树。 之所以用李超线段树，是可以想象出维护末项（k）和和 （b）之后最终的答案其实之和队对面的深度（x）有关，而这个大胆猜测可以...
2023-11-07
耳分解与双极定向
耳分解与双极定向 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132112802 耳分解 对于无向图中的任意边双和有向图中的任意强联通都可以按照此方法构造： S={u}S=\{u\}S={u} 每次找 SSS 的两个元素 u,vu,vu,v （可相同），找一条 不经过 SSS 的路径 ，并把路劲上的所有点加入 SSS 可以拿来dp，来构造某种条件的边双。 常用的状态设计 f(S)f(S)f(S) ，然后枚举 TTT 为 SSS 补集的子集。再...
2022-05-19
【P1948 [USACO08JAN]Telephone Lines S】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16289494.html 题目链接 题目 Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. The...
2021-12-03
【CF1110E Magic Stones】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640116.html 题目链接 我要是在noip前做这道题就好了。 这道题的本质就是noip2021方差中的一个性质，对于每个数进行修改，就是把它左右的差进行交换。 注意的是首项一定要一样。 Code 123456789101112131415161718192021222324252627282930313233343536373839// Problem: CF1110E Magic Stones// Contest: Luogu// U...