扫描线思想
扫描线思想
本文搬运自本人高中时期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
对于DP颜色类问题的切换方法：P9561
对于dp颜色类问题的切换方法：P9561 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471731 对于dp颜色类问题的切换方法 两种颜色为例，一般情况下 dp[i][0]dp[i][0]dp[i][0] 可以由 dp[j][0/1]dp[j][0/1]dp[j][0/1] 在某些情况下转移 但从0到0的过程中，对于 jjj 前的1，可能 jjj 满足，但 iii 不满足 此时可以考虑0只从1转移，1只从0转移，对于新的0，我们除了统计当前dp值，我...
2022-04-26
【CF580C Kefa and Park】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16195913.html 题目链接 题目 Kefa decided to celebrate his first big salary by going to the restaurant. He lives by an unusual park. The park is a rooted tree consisting of $ n $ vertices with the root at vertex $ 1 $ . Vertex $ 1 $ ...
2021-12-11
【P1661 扩散】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15674805.html 题目链接 题目 一个点每过一个单位时间就会向四个方向扩散一个距离，如图。 两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。 思路 二分答案+并查集。 首先二分时间 ttt。 如果两个点能直接相连，则他们的曼哈顿距离小于二倍 ttt。并且把...
2023-11-07
贪心转DP：AGC022E
贪心转DP：AGC022E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132152603 upd on 11.7 : 1的个数维护2个即可 https://www.luogu.com.cn/problem/AT_agc022_e 考虑如何选取是最优的，显然是000变0，110和010都是同时消掉01 观察此性质，可以发现0最多不会同时出现3个。对于第2种方法，在入0的时候我们不能确定是否还有连续0，但入1的时候可以确定前面没有连续0，所以在1的时候来维...
2023-08-08
zkw线段树
zkw线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132177887 启蒙题： http://zhengruioi.com/problem/2609 参考论文： https://wenku.baidu.com/view/f27db60ee87101f69e319544.html?wkts=1691491614153 不用递归，通过位运算实现的线段树。（本质：线段树为一颗满二叉树） 如果值域为 VVV ，那么zkw只能维护到 V−2V-2V−2 的值...
2026-06-16
算法复键——树状数组
算法复键——树状数组 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162026675 树状数组怎么被我忘光了？？？ 1. 干什么的 简单来说，树状数组支持一下两种操作： 单点加 查询前缀和 →\to→ 区间和查询 如果我们记录的是差分数列，那样子可以也可以实现： 区间加 单点查询 不一定是求和，所有满足交换律的都可以用树状数组实现。比如区间积、区间XOR 2. 怎么实现 现在以单点加、求前缀和为例： 我们定义一种操作 lowbit...