CF1896

A

$\color{red}{\texttt{cmk666}}$ 不会做，找我 py /cf/cf。结论是 $a_1=1$。

$\texttt{code}$

B

第一个出现的 $\texttt{A}$ 到最后一个出现的 $\texttt{B}$，特判 0。

$\texttt{code}$

C

经典结论题，排序后 $a$ 前 $x$ 个匹配 $b$ 后 $x$ 个，$a$ 后 $n-x$ 个匹配 $b$ 前 $n-x$ 个。证明略。

$\texttt{code}$

D

重题。P6859 蝴蝶与花弱化版。我的做法是线段树二分找到长度，再判对应调整区间内有没有 $1$。后来才发现可以直接用 set。。。

$\texttt{code}$

E

观察到如果 $i\to a_i$ 路径上有 $j\to a_j$ 路径被覆盖，那么就可以对步数产生 -1 的贡献，然后直接环形二维数点。

$\texttt{code}$

F

只要 $3$ 次。我们去头去尾将序列两两分为一组，注意到可以同时修改或同时不改一组的两个。
因此我们将 $\texttt{00}$ 和 $\texttt{11}$ 改为 $\texttt{11}$，将第奇数个 $\texttt{01}$ 和 $\texttt{10}$ 改为 $\texttt{01}$，偶数个改为 $\texttt{10}$。

然后，我们发现去头去尾后数组里 $\texttt{1}$ 的连续段长度都是偶数。考虑如下 $\texttt{pattern: ((()...()))}$ 可以将 $\texttt{1011...1101}$ 修改为全 $\texttt{0}$，因此对于两端都是 $\texttt{0}$ 的 $\texttt{1}$ 连续段使用这个 $\texttt{pattern}$，否则直接 $\texttt{)()()...(}$ 即可。

最后，如果头尾还是 $1$，则操作一次 $\texttt{(()...())}$ 即可。
从上述过程发现，当且仅当开始时 $1$ 的个数为奇数，或 $s_1\neq s_{n\times2}$ 时无解。

$\texttt{code}$

G

非常好题目，左我的宾格破碎。

首先，$n$ 个分一块找出最大值，再将每块最大值找出最大值就可以找出全局最大值。
然后，将这块最大值删去，从别的块的最大值之外的东西里贺几个过来补满 $n$ 个，再查询一次，就可以更新这块的最大值。
然后就做完了当然没有。

注意到最大值之外元素只有 $n-1$ 个时就没办法这么做了。但是成为每组的最大值的必然不是后 $n-1$ 小的，因此剩下 $n$ 个每组最大值就是后 $n$ 个答案。因此直接选择排序。

然后计算下步数。一开始操作 $n$ 次建块，然后找 $n^2-2n+1$ 次，每次两步，最后找 $n-1$ 次。总共 $2\times(n^2-2n+1)+n+n-1=2n^2-2n+1$ 次，刚好卡满上限。

$\texttt{code}$