善用值域数据结构+操作离线：1864F
善用值域数据结构+操作离线：1864F
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132631673
发现题目中有两个维度：
-
维护数值，发布计算某种情况下的答案
-
多个查询
两个维度，发现很难分开做。考虑对操作离线，同时维护两个维度的东西。
类似线段操作，左边入时±，右边出时-+
本质是一种扫描线的思想
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-21
数据结构中的判定转状态+扫描线：P1502
数据结构中的判定转状态+扫描线：P1502 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133124669 https://www.luogu.com.cn/problem/P1502 发现正常扫描线很难维护恰好大小为 WWW 的区间 反过来，对于每个星星维护合法的左下角下标 把原先的判定转成了和点有关的状态，把点变成矩形后求并即可 12345678910111213141516171819202122232425262728293031323334353...
2023-11-06
珂朵莉树转化区间（对于多区间类问题）+扫描线线段树维护：1031T3
珂朵莉树转化区间（对于多区间类问题）+扫描线线段树维护：1031T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134249552 http://cplusoj.com/d/senior/p/SS231031C 珂朵莉树有个很好的性质： 任意时刻，所有区间都是不交的 所以我们可以把所有区间先拿珂朵莉树变成一堆小区间，每个区间有个存活时间 [t1,t2][t_1,t_2][t1,t2] 考虑这个区间意义。他会在 l∈[1,t1],r∈[t1,t2]...
2023-11-13
全局操作区间查询——转前缀和+主席树维护
全局操作区间查询——转前缀和+主席树维护 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134369593 https://www.luogu.com.cn/problem/P9388 场上疯狂想分块，降智了 发现全局修改，区间查询，可以考虑前缀和 现在考虑维护某个时间戳的前缀。 我们现在有初始前缀所有数和前 qqq 次操作的所有数，我们要删掉前 qqq 大的数。 发现有值域和操作顺序 / 位置两个限制，考虑可持久化 发现维护三个很难，我们就拆成两棵线段树...
2021-11-16
【P2325 [SCOI2005]王室联邦】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15564095.html 题目链接 题目 “余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。 他的国家有 NNN 个城市，编号为 1…N1\ldots N1…N。 一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。 为了防止管理太过分散，每个省至少要有 BBB 个城市。 为了能有效的管理，每个省最多只有 3×B3\times B3×B 个城市。 每个省必须有一个省会...
2023-08-29
动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护：1192B
动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护：1192B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132566345 https://www.luogu.com.cn/problem/CF1192B 对于直径的求法，常用dp或两次dfs，但如果要动态维护似乎都不太方面，那么可以维护树上路径最大值。 树上路径为： depu+depv−2×deplca(u,v)dep_u+dep_v-2\times de...
2023-08-10
李超线段树
李超线段树 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217504 插入过程中，先询问中点，让 uuu 在上，它必然覆盖其中一个区间。 然后看看左右端点哪里 vvv 比 uuu 大，就在对应区间递归下去