其实 A 到 F2 都不是难题，但 D 和 F2 都没过，说明比赛方法和策略上需要调整。比以前好的地方在于，现在赛时更加稳扎稳打，而不是总想着抢过一道题，这样赛时就更加冷静了。

A

容易发现当且仅当对面大于自己时产生交换，所以观察 的奇偶性即可。

B

结论：最后的划分要么是一段和为 的段，要么是单个字符。

证明不难。如果一个段不都是用一种字符，那一定能找到一个和为 的子段，划出来显然更优。都是同一种字符则划分成单个字符显然更优。

于是可以 ，设 表示划分 的代价，转移显然。也可以注意到答案就是所有数和的绝对值。

C

设 表示到了第 位，与 所在序列不同的那个序列的末尾元素为 。可以用线段树维护第二维，支持全局加，单点修改，查前缀/后缀 min 即可。

D

太难了。

显然一棵树有恰好一个 的点。

考虑 的点到根的链，显然两边的点是若干个子树，且这些子树到根都有条长为 的边。将两边都减 后继续递归下去。在第一次递归之后，区间中可能有多个 的点，显然它们各自恰好对应原来那若干个子树 中的某一个。我们把这些 的点提出来，设有 个，序列被分成 段，从这 段继续递归下去即可。

核心代码如下：

bool FLG = 1;
void Solve(int l,int r,int ad) {
	if(l > r) return;
	vector<int> pps;
	int now = Qmin(l,r);
	if(a[now] > ad) FLG = 0;
	pps.push_back(l - 1);pps.push_back(now);
	while(now < r && a[Qmin(now + 1,r)] == ad) pps.push_back(now = Qmin(now + 1,r));
	pps.push_back(r + 1);
	for(auto i = 0;i + 1 < pps.size();i++)
		Solve(pps[i] + 1,pps[i + 1] - 1,ad + 1);
}

E

转化一下题意：计数长度为 的序列 个数，满足 ，其中 恰好出现 次。

实际上这个 序列就是排序前的前缀和数组。

直接大力连续段 DP 即可。设 表示当前从小到大填到值为 的元素，一共形成 个连续段，最左边是不是 ，最右边是不是 。

转移分讨即可，与 ARC146E 一模一样。注意判断序列最左端是不是 。

ARC146E 题解：https://dualqwq.github.io/posts/302081082/

F

先考虑没有 的限制怎么做。考虑维护当前水量 ，显然知道了 的最终值后容易算出答案。那么过一个塔之后 。对于这种不断对 取 max 的变化过程，我们有个经典转化：不妨允许 变化到负数，那么此时 的历史最小值实际上就是原来 与 ckmax 时被抬升的高度之和。这个值实际上也是每次过水塔时， 比 多出来的部分之和。(注意这个历史最小值是非正的，但被抬升高度是非负的，所以实际上应该是相反数)

那么答案就是 加上 的最小前缀和，线段树容易维护。

接着考虑有 的限制怎么做。

其实跟上文关系不大。

建出一张 个点的网络流图： 向 连流量为 的边， 向 连流量为 的边， 向 连流量为 的边。容易发现这张图的最大流就是问题答案。

利用最大流/最小割定理将其转化为最小割。显然每个点要么与 连通，要么与 连通，分别记为 点和 点。相邻的 和 之间的那条长为 的边必须割掉（但 在前 在后时不需要）。除此之外每个点成为 点和 点还有各自的代价。所以设 表示前 个点的最小割，第 个点是 点/ 点。那转移如下： 有单点修改，每个点维护一个 的转移矩阵，动态 DP 即可。

总结

在大概 分钟的时候过了 ABCE 与 F1，当时及时地跳过了 D。后来就在想着，D 与 F2 同分，而 D 过的人数远大于 F2，我只要把 D 磕出来就行了。后来发现剩下的时间对 D 并没有非常有效而深入的思考，也没有去做 F2，赛后才发现 F2 对自己来说非常简单。

主要问题在于：

1. 给自己设立了”不打算做 F2" 的心理限制。
2. 对 D 这种找充要条件的题目不是很擅长，或者说在赛场上对这种题难以思路清晰。