交错序列——差分：GZOI2023D2T3
交错序列——差分：GZOI2023D2T3
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133247058
单点修改，全局查询交错序列最大值（ ）， 为 的子序列
正常做法是线段树，但对于交错序列问题，有一种更好的方法，就是差分
考虑 ，本质就是 的差分数组之和。由于选的段数没有限制，那必然是全选正数
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
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...
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...
2026-10-17
杨图计数 + 对角线性质 + 轮廓线计数 + 差分：ICPC2025沈阳H
杨图计数 + 对角线性质 + 轮廓线计数 + 差分：ICPC2025沈阳H Cute Young Diagram Counting - Problem - QOJ.ac 我们首先思考一下，翻转操作中，什么是不变的。 假设一个格子在 (i,j)(i,j)(i,j)，我们让其贡献到 ti+jt_{i+j}ti+j 里。不难证明，ttt 序列是始终不变的。 ttt 序列的形式必然是：0,1,x,y,⋯ ,z,0,0,⋯0,1,x,y,\cdots,z,0,0,\cdots0,1,x,y,⋯,z,0,0,⋯ 接下来我们证明，所有满足此 ttt 序列的杨图必然是可以构造出来的。 首先，所有操作...
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...
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...
2026-10-07
二阶差分生成函数优化dp + NTT + cdq优化NTT：CCPC2026网络赛G
二阶差分生成函数优化dp + NTT + cdq优化NTT：CCPC2026网络赛G Growing Prefix Span - Problem - QOJ.ac 哭了，这道题调了10多个小时，打了无数个补丁，终于调出来了 好，首先一开始肯定是要处理一下 [Li,Ri][L_i,R_i][Li,Ri]，变成合法区间，然后判断一下无解。 然后我们可以列一个很显然的 O(n2)O(n^2)O(n2) 的dp。f(i,j)f(i,j)f(i,j) 代表前 iii 个数长为 jjj，显然有： f(i,j)=f(i−1,j)×(j−i+1)+2∑k<jfi−1,kf(i,j)=f(...