交错序列——差分：GZOI2023D2T3
交错序列——差分：GZOI2023D2T3
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133247058
单点修改，全局查询交错序列最大值（ ）， 为 的子序列
正常做法是线段树，但对于交错序列问题，有一种更好的方法，就是差分
考虑 ，本质就是 的差分数组之和。由于选的段数没有限制，那必然是全选正数
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-12-21
【USACO2021 Convoluted Intervals 】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15716558.html 题目 The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of NNN intervals (1≤N≤2⋅1051\le N\le 2\cdot 10^51≤N≤2⋅105), where the iiith interval star...
2021-11-24
【NOIP2021 方差】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15598937.html 题目链接 Part A 式子化简 首先题目要求的式子就是 n2n^2n2 乘上 1n∑i=1n(ai−aˉ)2\frac{1}{n}\sum_{i=1}^n(a_i-\bar a)^2n1∑i=1n(ai−aˉ)2，其中 aˉ=1n∑i=1nai\bar a=\frac{1}{n}\sum_{i=1}^n a_iaˉ=n1∑i=1nai。 我们把这三合在一起也就是： n2×1n∑i=1n(ai−1n∑j=1n...
2026-07-19
《具体数学》2 Sum Study Note (2)
《具体数学》2 Sum Study Note (2) Repertoire method If we want to calculate : ∑i=1ni2\sum_{i=1}^n i^2∑i=1ni2, we can construct a recursion : {R0=αRn=Rn−1+β+γn+δn2\begin{cases} R_0 = \alpha \\ R_n = R_{n-1} + \beta + \gamma n + \delta n^2 \end{cases} {R0=αRn=Rn−1+β+γn+δn2 And it must satisfy : Rn=A(...
2021-12-03
【CF1110E Magic Stones】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15640116.html 题目链接 我要是在noip前做这道题就好了。 这道题的本质就是noip2021方差中的一个性质，对于每个数进行修改，就是把它左右的差进行交换。 注意的是首项一定要一样。 Code 123456789101112131415161718192021222324252627282930313233343536373839// Problem: CF1110E Magic Stones// Contest: Luogu// U...
2023-11-16
对于从三个方向转移的期望DP式子移项方法
对于从三个方向转移的期望dp式子移项方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133753059 fi=afi−1+bfi+cfi+1+vif_i=af_{i-1}+bf_i+cf_{i+1}+v_ifi=afi−1+bfi+cfi+1+vi ，其中 a+b+c=1a+b+c=1a+b+c=1 ，求 fff 考虑差分， gi=fi−fi+1g_i=f_i-f_{i+1}gi=fi−fi+1 fi=a(fi−1+gi−1)+bfi...
2023-09-11
Kruskal重构树+AC自动机+树状数组：Gym - 104542F
Kruskal重构树+AC自动机+树状数组：Gym - 104542F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818179 https://vjudge.net/contest/579844#problem/F 看到连边和没有强制在线，考虑Kruskal重构树 看到判断子串，考虑AC自动机+线段树 然后要非常大胆地把两个结合起来。 然后就是大码量了。 具体总结一下流程： 先建出Kruskal重构树 对Kruskal重构树处理...