【题解】CodeForces-1913-526互联

CodeForces-1913A Rating Increase

依题意模拟。

交换免费就是能任意重排，从头开始尽量填相反的，剩下只能删去了。

从大到小能减则减一定更优。

认为两次操作覆盖到同一元素是操作有交，发现这等价于取并区间操作一次，没有被操作的可以视作对自己操作，那么就是划分若干区间，每个区间只保留最小值，求本质不同方案数。

设 \(f_i\) 表示以 \(i\) 为最后一个区间的最小值的方案数，枚举上一个区间的最小值 \(j\)，充要条件是 \(\min(p_i,p_j)=\min_{k=j}^i \{p_k\}\)。

若 \(p_i<p_j\)，即 \(pos_i\) 为序列中第一个小于 \(i\) 的位置，则 \(j\in [pos_i+1,i-1]\)，可以前缀和转移。

若 \(p_i>p_j\)，那么 \(p_j\) 是 \([j,i]\) 的最小值，发现这就是当前单调栈内所有元素，维护一个和即可。

首先 \(\sum A_i=\sum B_j\)，考虑左部点为行，右部点为列的二分图，假设先把所有 \(1\) 翻成 \(0\)，这样这些位置翻成 \(0\) 的费用是 \(-1\)，其他位置是 \(1\)，跑一个最小费用最大流即可。

如果担心出负圈可以权值都加 \(1\)，最后答案再减去最大流。注意无解也要靠最大流是否等于 \(\sum A_i\) 判断。