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-10-18
set维护连续段+线段树：1018T2
set维护连续段+线段树：1018T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133914164 http://cplusoj.com/d/senior/p/386?tid=652f5fe6c1fe41bc229c18fb 线段树维护01，和，支持翻转操作 用类似珂朵莉树的方法维护连续段，连续段之间分别统计，取max 1234567891011121314151617181920212223242526272829303132333435363738...
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值，我...
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-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]...
2024-10-07
1007B逆序对（二维数点问题 窗口星星）
1007B逆序对（二维数点问题 窗口星星） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142741239 http://cplusoj.com/d/senior/p/SS241007B 显然这题是一个二维数点问题，我们要求在确定 [l,r][l,r][l,r] 下 iii 个数的最大值： l<i<rl<i<rl<i<r ar<i<ala_r<i<a_lar<i<al ...
2023-10-08
ds套DP——考虑位置转移or值域转移：CF1762F
ds套dp——考虑位置转移or值域转移：CF1762F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133691573 https://www.luogu.com.cn/problem/CF1762F 分析性质，就是我们选的数要么递增，要么递减（非严格） 然后很明细是ds套dp， fif_ifi 表示以 iii 开头的答案 然后考虑如何转移（ds套dp难点反而在转移而不是状态，因为要考虑如何和ds结合） 转移的话，要么从位置考虑，要么从值...