2026
0224
A分糖果
推下上下界充要条件，两次二分，树状数组check，时间复杂度 \(O(nlog^2n)\)。
B排列切割
注意到满足前缀i复原时，用至多两次操作能将i+1复原，且操作方案唯一，那么这一定是划分的最优决策。
接下来考虑两次操作间的一次操作为什么。
情况A：某一块分成两块，将后半块放到前面的一个位置。某块可以拆分的条件为此块的最小值不是开头。
情况B：某一块分成两块，将后半块放到后面的一个位置。某块的拆分条件为此块内的最大值要大于下一块的开头。
AB情况一定不会插在同一个位置，所以只用判第一个改变位置的大小关系就可以了。
实现上：
用两个set分别维护切割点的下标集合和权值集合，用一颗权值线段树维护答案，其中在分割点的位置记录段长和哈希值。
Random Walk
通过期望的线性性将经过的本质不同的格子数变成每步到达未到过的点的概率之和，容斥一下，变成计算到过的点的概率，相当于最后走了一个环。
于是现在需要计算 \(g_i\) 表示从原点出发，走i步第一次回到原点的概率。再记一个 \(f_i\) 表示从原点出发，走i步回到原点的概率，两个数组可以简单递推。