交错序列——差分：GZOI2023D2T3
交错序列——差分：GZOI2023D2T3
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133247058
单点修改，全局查询交错序列最大值（ ）， 为 的子序列
正常做法是线段树，但对于交错序列问题，有一种更好的方法，就是差分
考虑 ，本质就是 的差分数组之和。由于选的段数没有限制，那必然是全选正数
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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...
2023-10-09
差分构造法推广：arc166_d
差分构造法推广：arc166_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133694378 https://atcoder.jp/contests/arc166/tasks/arc166_d 首先肯定是这样子放： 考虑相邻之间的差，本质就是橙色区间减蓝色区间数量 区间数量越少显然越优，所以我们要么保留橙区间，要么保留紫区间，然后两两匹配 12345678910111213141516171819202122232425262728293031323...
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重构树处理...
2021-12-08
【HDU 7015 Another String】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15663221.html 题目链接 题目 Define the distance between two strings of the same length as the numbers of the positions where the characters differ in these two strings. If two strings of the same length has a distance of no more tha...
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-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...