善用值域数据结构+操作离线：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]...
2021-12-05
【P1717 钓鱼】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15645444.html 题目链接 题目 话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽，为了表示安慰和鼓励，VIP999 决定请他吃一次“年年大丰收”，为了表示诚意，他还决定亲自去钓鱼。 但是，因为还要准备 NOIP2013, z老师只给了他 HHH 个小时的空余时间，假设有 nnn 个鱼塘都在一条水平路边，从左边到右编号为 1, 2, 3 … n 。 VIP是个很讲究效率的孩子，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向...
2022-04-22
【GDOI2022PJD1T1 邹忌讽齐王纳谏】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16179574.html D1T1 邹忌讽齐王纳谏 题目 齐国人邹忌对齐国国君齐威王说，大王身边的人会因为私情、利益等原因而对大王阿谀奉承，所以不能光听好话，只有广泛接受群众的批评意见，才不会被蒙蔽双眼，齐国才能强盛。齐威王接受了这个意见，于是昭告全国： 如果有臣民当面对齐威王提出建议，则获得价值为 A 的奖励； 如果有臣民以书信的方式对齐威王提出建议，则获得价值为 B 的奖励； 如果有臣民在街市中议论齐威王，意见流传到宫廷，则获得价值为 C ...
2023-12-19
势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446
势能相关难维护的用分块——分块过程维护跨块的：CF1491H / P7446 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135093792 https://www.luogu.com.cn/problem/P7446 https://www.luogu.com.cn/problem/CF1491H 看到题，发现只有减，就和势能有关。维护势能，像这种题，树形ds显然不好做，所以可以去考虑进行分块。 考虑分块。每个块记录一个 bib_ibi ， iii 的...
2023-08-05
线段树分治
线段树分治 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126153 https://www.luogu.com.cn/problem/P5787 理解： 操作离线 用时间线段树维护 整体统计答案，进入到某个节点加入，离开时撤销 可以用可撤销数据结构维护（可能可以可持久化或LCT维护？以后再学）