CF1860

A.

构造 $()\times n$，$(\times n + )\times n$。

B.

模拟。

C.

定义 I 类点：左边没有一个比他大的。

如果起点在 $i$，左边只有 I 类点，那么这个 $i$ 是一个合法的起点。

edu 的时候写了个 rmq，感觉自闭了。

事实上只要维护前面的最大值，还有合法点的最小值可以了。

模拟。

D.

首先考虑，一个点最多被交换一次（显然）。也就是相当于改变的点的个数 / 2。

考虑 $dp_{i, j, k}$ 为前 $i$ 个里面有了 $j$ 个 1且 $k = cnt_{10} - cnt_{01}$ 时候最少需要改变几个数字。

最后答案为 $dp_{n, cnt_1, 0} / 2$。dp 可以滚动数组，能过。

没看太懂别人的做法。

E.

其实就是两个操作，之前 cf 出过一次（x

• 走到相邻的点
• 走到颜色相同的点

代价都是 1。

做法: 可以多源最短路，定义 $dis_{col,i}$ 表示颜色 $col$ 走到 $i$ 需要多少次操作。

最后的答案是 $\min {\min dis_{col,x} + dis_{col,y} + 1, |x - y|}$。

+1 是相同颜色间转移，**如果是相同颜色是同一个点，那么不会在这个点是最小值，而是在别的颜色走操作二的时候更新答案，或者答案就是 |x-y|**。

F.

差不多懂了 heltion 的做法。

首先我们要知道合法的括号序列有两个要求。

• 左右括号数量相等。
• 左括号在任何时候数量大于等于右括号。

对于第一点，题目保证了，对于第二点，把左括号看成 1，右括号看成 -1，前缀和不存在负数即可。

然后我们考虑这个题，先做一点微小处理，把相同的当成一个，也就是 map[(a, b)] += c。

我们大概可以知道，需要枚举的 $(x,y)$ 有 $n^2$ 种，

edu 场上的时候想到了应该要枚举 $k = y/x$，然后把所有的点按照权值 $a_i + b_i \times k$ 来排序，但是因为用的是实数，所以疯狂 wa 2。

然后 heltion 的做法是: 把所有 $k$ 和与 $k$ 有关的 $(i, j)$ 塞进 map 里，按照 $k$ 来排序，（k 是从小到大的）。

默认 $k = eps$，也就是直接直接按照 $a_i$ 为第一关键字，$b_i$ 为第二关键字来排序。

然后开始从小到大枚举 $k$，每次把与 $k$ 有关的所有位置提取出来（发现位置是连续的一段），并计算 $a_i + b_i \times k$，然后把相同的 $a_i + b_i \times k$ 内部先按照左括号优先的原则排好，然后计算相关的贡献。

最后权值相同的点用 $b_i$ 来排序，因为后续的 $k$ 越来越大，也就是 $b_i$ 越大权值会越大，这样可以 保证后面选择的位置也是连续的一段。