题解：CF2077E Another Folding Strip

怎么都不是这么做的？？？

先考虑计算 $f(a_1,a_2,\cdots,a_n)$。

考虑一次折叠相当于将编号为 $p_1<p_2<\cdots<p_k$ 的格子减一，然后要求 $p_i$ 和 $p_{i-1}$ 奇偶性不同。

考虑构建一张二分图，其中左部点表示入度，右部点表示出度。入度 $i$ 能和出度 $j$ 匹配，当且仅当 $j<i$，且$i,j$ 奇偶性不同。

那么最少操作次数，就等价于 $\sum_{i=1}^{n} a_i-\text{maxmatch}$。

计算 $\text{maxmatch}$ 考虑 Hall 定理，对于权值，我们可以等效看成多个点，令 $L$ 表示左部点集合，$N(S)$ 表示 $S$ 集合出边的并集。由于 $\text{maxmatch}=|L|-\max_{S\subseteq L}\{|S|-|N(S)|\}$，所以最少操作次数为 $\max_{S\subseteq L}\{|S|-|N(S)|\}$。

对于 $N(S)$，我们发现我们只关心 $S$ 集合中的编号最大值 $mx_1$，以及编号和 $mx_1$ 奇偶性不同的编号最大值 $mx_2$。我们发现，$mx_2$ 前面的位置选，不会对 $N(S)$ 造成影响，同时 $(mx_2,mx_1]$ 之间和 $mx_1$ 奇偶性相同的位置，也不会对 $N(S)$ 产生影响。于是，为了使得 $|S|$ 尽量大，我们会将这些点全选。

我们发现此时 $S$ 为 $\{i|i\le mx_2\}\cup\{i|i\in[mx_2,mx_1]\land i\equiv mx_1\pmod 2\}$，$N(S)$ 为 $\{i|i\le mx_2\}\cup\{i|i\in(mx_2,mx_1]\land i\not\equiv mx_1\pmod 2\}$。

那么 $|N(S)|-|S|$ 就为：

就得到了这个重要结论。

然后，我们发现，如果单纯是求最大区间偶数位置和减奇数位置和，是Treasure Hunt，所以一定有玄机。

我们考虑令 $s_i$ 为前 $i$ 个数，奇数位置减去偶数位置的差。

那么我们惊讶的发现，求的东西就可以等效成 $\max_{i=l-1}^{r} \{s_i\}-\min_{i=l-1}^{r} \{s_i\}$。

于是拆成两部分，单调栈维护了。