D. Balanced Array \(\star\)
赛时做法
枚举前缀维护合法的 \(k\)
感性上 \(k\) 越大需要满足的式子越少，只保留最大的 \(\log\) 个 \(k\)，可以通过
std
枚举 \(k\)，合法的 \(l\) 一定是一个左端点为 \(2k+1\) 的区间，二分右端点
等式 \(\forall1\le i\le l-2k,a_{i}+a_{i+2k}=2a_{i+k}\) 两边都是关于 \(a_i\) 的线性函数，等价于判断 \(hash(1,l-2k)+hash(1+2k,l)=2hash(1+k,l-k)\)
从小到大枚举 \(k\)，对应合法区间的左端点递增，某种意义上可以看作对应一个合法前缀。维护已知合法的最长前缀 \(l\)，尝试用当前 \(k\) 延申 \(l\)
时间复杂度 \(O(n)\)
K. Campus Partition \(\star\)
“连通块次大值”是难以刻画的信息，注意到可以只保留最大值到次大值的链，转化为“链端点较小值”
考虑 dp，在 lca 处合并链。设 \(f[u,i]\) 表示子树 \(u\)、经过 \(u\) 的链一端权值为 \(i\) 的答案，\(g[u]\) 为子树 \(u\) 的答案
\[f[u,i]=\max(f[u,i]+g[v],\sum_{w\text{ is }u\text{'s son before }v}g[w]+f[v,i]) \]\[g[u]=\max(g[u]+g[v],f[u,i]+f[v,j]+\min(i,j)) \]线段树合并维护
标签：前缀,题解,大值,合法,枚举,端点,2023,ICPC,2k From： https://www.cnblogs.com/ft61/p/18393689