ST表倒序释放：1019T1
ST表倒序释放：1019T1
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133926195
http://cplusoj.com/d/senior/p/SS231019A
发现只有修改，最后查询，且区间取max，可以考虑维护类似ST表的过程
把 拆成前后两个区间，分别在ST表修改
最后ST表从上往下释放即可
复杂度
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-15
+-1 RMQ
±1 RMQ 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132906556 考虑分块 令 b=log2n2b=\frac{\log_2 n}2b=2log2n ，按 bbb 分块 使用ST表处理大块间的 RMQ 问题 对于一个块内的 RMQ 问题，由于差分数组 2b−12^{b−1}2b−1 种，可以预处理出所有情况下的最值位置 12345678910111213141516171819202122232425262728293031323334v...
2023-12-13
信息合并类+ST表：CF1707E
信息合并类+ST表：CF1707E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134982534 https://www.luogu.com.cn/problem/CF1707E f([l1,r1]∪[l2,r2])=f(l1,r1)∪f(l2,r2)f([l_1,r_1]\cup [l_2,r_2])=f(l_1,r_1)\cup f(l_2,r_2)f([l1,r1]∪[l2,r2])=f(l1,r1)∪f(l2,r2) f([l1,...
2023-10-06
珂朵莉树维护并查集：CF1725K
珂朵莉树维护并查集：CF1725K 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133607729 https://codeforces.com/problemset/problem/1725/K 发现题目涉及值域的区间覆盖，可以考虑对值域维护珂朵莉树（应该是类似珂朵莉树思想的东西）。 但要把值域对应回原位置，我们可以拿并查集维护。 12345678910111213141516171819202122232425262728293031323334353...
2023-08-24
运用时间线段树对树上问题进行离线处理
运用时间线段树对树上问题进行离线处理 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471723 运用时间线段树对树上问题进行离线处理 对于树上问题，有时候离线处理更优，但要维护操作之间的有序性，可以考虑用时间线段树维护。 例题：CF383C
2022-02-17
【P2569 [SCOI2010]股票交易】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905849.html 题目链接 题目 最近 lxhgww\text{lxhgww}lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。 通过一段时间的观察，lxhgww\text{lxhgww}lxhgww 预测到了未来 TTT 天内某只股票的走势，第 iii 天的股票买入价为每股 APiAP_iAPi，第 iii 天的股票卖出价为每股 BPiBP_iBPi（数据保证对于每个 iii，都有 APi≥BP...
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 个城市。 每个省必须有一个省会...