[CF2188C] Restricted Sorting

这道题目我疑似是假做法，就直接搬运官方题解了，补充了一些证明。

考虑 aa 排序后的数组是 bb，那么对于 ai=bia_i=b_i 的位置 ii 我们不需要管它，于是我们找到 ai≠bia_i\neq b_i 的位置，并且记录下来最大值和最小值 mx,mnmx,mn。

这里一定有 mn≠mxmn\neq mx，否则，这些元素是同一个值，并且除了这些元素之外的元素都已经排序完成了，那么比它大的元素在正确的位置，比它小的元素同理，那么这一些元素又是相等的，它们必然在正确的位置。

然后，对于所有 ai≠bia_i\neq b_i 的位置，如果 mx−ai<kmx-a_i<k 且 ai−mn<ka_i-mn<k，那么 aia_i 与任意元素都不可换，此时的 kk 是非法的。

所以，对于所有 ai≠bia_i\neq b_i 的位置，必须有 mx−ai≥kmx-a_i\ge k 或 ai−mn≥ka_i-mn\ge k 成立，此时我们可以证明对于任意的 i,ji,j 满足 ai≠bi,aj≠bja_i\neq b_i,a_j\neq b_j 的位置，它们都是可以交换的：

  1. 如果 ai,aja_i,a_j 是 mxmx 和 mnmn，它们一定可换。
  2. 否则，ai,aja_i,a_j 和 mx,mnmx,mn 其中之一都可换，直接通过 mxmx 或者 mnmn 交换即可。容易看出，如果 ai,aja_i,a_j 其中之一是 mx,mnmx,mn 另一个不是的话，是落在这一个条件里的。
  3. 否则，不妨设 aia_i 与 mxmx 可换，aja_j 与 mnmn 可换，那么它们分别交换之后交换 mx,mnmx,mn 再交换回去，就能通过 mx,mnmx,mn 交换 ai,aja_i,a_j。

所以这是一个充要条件。

[CF2188D] Shortest Statement Ever

我没看懂官方题解，这里说一下我怎么做的，设 BB 是 x,yx,y 的二进制位数量。

分类讨论四种情况，0≤p≤x,p>x0\le p\le x,p>x 与 0≤q≤y,q>y0\le q\le y,q>y 组合一下，有 2×2=42\times 2=4 种情况，又因为有两种情况是互相对称的，所以只需要讨论三种情况：

  1. 当 0≤p≤x,0≤q≤y0\le p\le x,0\le q\le y 时，∣x−p∣+∣y−q∣=x+y−(p+q)|x-p|+|y-q|=x+y-(p+q)，我们只需要求出 p+qp+q 的最大值。

    又因为 p∩q=∅p\cap q=\varnothing，所以 p+q=p⊕qp+q=p\oplus q。

    根据贪心的思路，我们从高向低枚举每一个位，设 x,yx,y 这一位上分别是 X,YX,Y。

    1. 如果 X=Y=0X=Y=0，那么只能填 00；
    2. 如果 X=0,Y=1X=0,Y=1，我们让 pp 的这一位填 11，给 p+qp+q 这一位贡献上了一个 11；
    3. 如果 X=1,Y=0X=1,Y=0，同上；
    4. 如果 X=Y=1X=Y=1，那么给 pp 填一个 11，给 qq 剩下的所有位都填 11，这样后续的所有位都是 11。

    根据二进制的性质，我们尽量填高位，并且让尽量填高位的同时后面能填的位全部填上了（遇到情况 44 之前能填则填，遇到情况 44 之后所有位都填），所以这就是 p+qp+q 能取到的最大值。

  2. 当 p>x,q>yp>x,q>y 时，∣x−p∣+∣y−q∣=p+q−x−y|x-p|+|y-q|=p+q-x-y，我们需要让 p+qp+q 最小。

    我们可以 O(B)O(B) 枚举 pp 从哪一位开始比 xx 大，那么从这一位往后全是 00 可以让 pp 最小的同时给 qq 留出最多的操作空间，此时再 O(B)O(B) 枚举 qq 从哪一位开始比 yy 大，注意满足 p∩q=∅p\cap q=\varnothing。

  3. 当 p>x,q≤yp>x,q\le y 时，∣x−p∣+∣y−q∣=p−q−x+y|x-p|+|y-q|=p-q-x+y，我们需要让 p−qp-q 最小。

    同上，也是 O(B2)O(B^2) 可以枚举出来的。

如果按照这个思路来，本题目较为扎实地考察了贪心的思想，也就是有些时候多个限制条件是可以被构造出来的某种特殊情况（即上面的让后面全是 00 这种操作）同时满足的。

[CF2188E] Jerry and Tom

本题的重要结论是，如果 ii 有多条出边，无论是 Jerry 还是 Tom，都会走对应节点最大的一条。

设 aia_i 是 ii 的所有出边中对应节点最大的那个节点，那么 ii 到达 nn 的路径必然经过 aia_i。

证明：假设 ii 到 nn 的路径上不经过 aia_i，说明 ii 的下一步 jj 不是 aia_i，又因为 aia_i 是 ii 的所有出边中对应节点最大的节点，那么 j<aij<a_i。设 jj 的下一步是 k(≠ai,k>j)k(\neq a_i,k>j)，那么：

  • 如果 k>aik>a_i，违背题目条件。
  • 如果 k<aik<a_i，令 j←kj\gets k，重复上述流程，必定再有限步内违背题目条件。

故命题得证，那我们可以构建一颗树，节点 ii 的父节点是 aia_i，根是 nn，每一个节点的深度是 did_i

根据我们上面的论述，ii 到 nn 的所有路径（不一定要走树边）都会经过 aia_i，那么 i∼ni\sim n 的任意一条路径都会包含这棵树上 i∼ni\sim n 路径上的所有节点。

假设 Jerry 在 xx，Tom 在 yy，并且 lca⁡(x,y)=u\operatorname{lca}(x,y)=u，那么 Jerry 不会被抓当且仅当 dx<dyd_x<d_y。

  • 当 dx<dyd_x<d_y 时，只要 Jerry 一直沿树边走，Tom 最快的速度也就是沿着树边走，是没有办法抓到 Jerry 的。
  • 当 dx≥dyd_x\ge d_y 时，Tom 以最快速度走到 uu 会比 Jerry 更先到达 uu（同时到达也视为更快），那么 Jerry 是一定会被抓的。

并且，我们可以知道，如果 Tom 未到达 uu，是无法抓住 Jerry 的；如果 Tom 到达了 uu，它没有必要继续往上走；在到达 uu 之前的所有路径中，走树边是最快的。所以说 f(x,y)=dy−duf(x,y)=d_y-d_u。

于是我们计算的值就有了：∑1≤x,y≤n,x≠y,dx≥dydy−dlca⁡(x,y)\sum_{1\le x,y\le n,x\neq y,d_x\ge d_y} d_y-d_{\operatorname{lca}(x,y)}。

因为原本的 (x,y)(x,y) 对要求了 x≠yx\neq y，于是要么 x>yx>y，要么 x<yx<y，我们可以只枚举 x<yx<y 的 (x,y)(x,y) 对，然后加上 (x,y)(x,y) 和 (y,x)(y,x) 两个对的贡献。

于是转化成了 ∑1≤x<y≤n(dx−dlca⁡(x,y))[dx≤dy]+(dy−dlca⁡(x,y))[dx≥dy]\sum_{1\le x<y\le n} (d_x-d_{\operatorname{lca}(x,y)})[d_x\le d_y]+(d_y-d_{\operatorname{lca}(x,y)})[d_x\ge d_y]。

我们知道 dxd_x 和 dyd_y 也只有三种关系，大于、小于和等于。

如果 dx=dyd_x=d_y，那么一个 (x,y)(x,y) 对会产生两个贡献，否则只会产生一个贡献。我们不妨都贡献一次，然后把满足 dx=dyd_x=d_y 的 (x,y)(x,y) 找出来再贡献一次，于是就转换成了 (∑1≤x<y≤nmin⁡(dx,dy))−(∑1≤x<y≤ndlca⁡(x,y))+(∑1≤x<y≤n,dx=dydy−dlca⁡(x,y))\left(\sum_{1\le x<y\le n} \min(d_x,d_y)\right)-\left(\sum_{1\le x<y\le n} d_{\operatorname{lca}(x,y)}\right)+\left(\sum_{1\le x<y\le n,d_x=d_y} d_y-d_{\operatorname{lca}(x,y)}\right)。

对于第一部分，我们只需要给 dd 数组排序之后就容易得出，注意后面我们还要用 dd 数组，所以实际上这是最后处理的；

对于第二部分，我们可以在第一遍 DFS 预处理时枚举每一个点作为 lca⁡(x,y)\operatorname{lca}(x,y) 然后统计满足条件的 (x,y)(x,y) 对；

对于第三部分，可以用 DSU On Tree 的思路，开一个关于 dd 的计数数组，枚举轻边下的子树中所有节点即可。

题解说了存在线性做法，但是我不会。

[CF2188F] Cool Problem

既然要求和，那么我们应当先求出 cic_i 某种意义上的通项公式，硬做的话显然有一些正负号相互抵消了，状态量太大。

问题是 cic_i 和 ci−1c_{i-1} 之间的关系式的系数不一定一样，我们需要用某种方式给它们统一，所以设 viv_i 满足这样的关系：

  • v0=1v_0=1；
  • 若 ri=0r_i=0，则 vi=vi−1v_i=v_{i-1}；
  • 若 ri=1r_i=1，则 vi=−vi−1v_i=-v_{i-1}。

于是，我们给 cic_i 和 ci−1c_{i-1} 的递推式就满足：

  • 若 ri=0r_i=0，则 civi=xvi−1+ci−1vi−1c_iv_i=xv_{i-1}+c_{i-1}v_{i-1}；
  • 若 ri=1r_{i}=1，则 civi=−yvi−1+ci−1vi−1c_iv_i=-yv_{i-1}+c_{i-1}v_{i-1}。

既然我们的 viv_i 已经分类讨论了，那么就不要再让 civi−ci−1vi−1c_iv_i-c_{i-1}v_{i-1} 分类讨论了，我们希望利用这个已经讨论后的量。

具体地说，我们希望一个关于 vi,vi−1v_i,v_{i-1} 的统一的式子 FF 和 civi−ci−1vi−1c_iv_i-c_{i-1}v_{i-1} 的值相等，即：

  • 若 vi=vi−1v_i=v_{i-1}，则 F=xvi−1F=xv_{i-1}；
  • 若 vi=−vi−1v_i=-v_{i-1}，则 F=−yvi−1F=-yv_{i-1}。

可以待定系数法构造出 F=x+y2vi+x−y2vi−1F=\cfrac{x+y}{2}v_i+\cfrac{x-y}{2}v_{i-1} 符合条件，于是我们就有：

civi−ci−1vi−1=x+y2vi+x−y2vi−1civi−c0v0=x+y2∑j=1ivj+x−y2∑j=0i−1vj\begin{aligned} c_iv_i-c_{i-1}v_{i-1}&=\frac{x+y}{2}v_i+\frac{x-y}{2}v_{i-1}\\ c_iv_i-c_0v_0&=\frac{x+y}{2}\sum_{j=1}^i v_j+\frac{x-y}{2}\sum_{j=0}^{i-1} v_j\\ \end{aligned}

设 Si=∑j=1ivjS_i=\sum_{j=\bold{1}}^i v_j，那么我们有 civi=x+y2Si+x−y2Si−1+x−y2c_iv_i=\cfrac{x+y}{2} S_i+\cfrac{x-y}{2}S_{i-1}+\cfrac{x-y}{2}，注意 v0=1v_0=1。

又因为 vi=±1v_i=\pm1，所以 ci=civi2c_i=c_iv_i^2，于是我们可以继续写出 f(r)f(r) 的表达式：

f(r)=∑i=1ncivi2=∑i=1nx+y2Sivi+x−y2Si−1vi+x−y2vi=x−y2Sn+∑i=1nx+y2Si2−x+y2SiSi−1+x−y2SiSi−1−x−y2Si−12=x−y2Sn+∑i=1nx2(Si2−Si−12)+y2(Si2+Si−12−2SiSi−1)=xSn2+(x−y)Sn+ny2\begin{aligned} f(r)&=\sum_{i=1}^n c_iv_i^2\\ &=\sum_{i=1}^n \frac{x+y}{2} S_iv_i+\frac{x-y}{2}S_{i-1}v_i+\frac{x-y}{2}v_i\\ &=\frac{x-y}{2}S_n+\sum_{i=1}^n \frac{x+y}{2} S_i^2-\frac{x+y}{2}S_iS_{i-1}+\frac{x-y}{2}S_iS_{i-1}-\frac{x-y}{2}S_{i-1}^2\\ &=\frac{x-y}{2}S_n+\sum_{i=1}^n \frac{x}{2}(S_i^2-S_{i-1}^2)+\frac{y}{2}(S_i^2+S_{i-1}^2-2S_iS_{i-1})\\ &=\frac{xS_n^2+(x-y)S_n+ny}{2} \end{aligned}

于是 f(r)f(r) 可以被 SnS_n 唯一确定。SnS_n 的值域只是 [−n,n][-n,n]，我们可以动态规划求出 SnS_n 的所有可能取值。

具体地说，令 dp1dp_1 表示当前 vi=1v_i=1 时 SnS_n 的所有取值构成的集合，dp2dp_2 表示当前 vi=0v_i=0 时 SnS_n 的所有取值构成的集合，然后根据 rir_i 的不同在 dp1,dp2dp_1,dp_2 相互进行转移即可，用 bitset 优化可以做到 O(n2/ω)O(n^2/\omega)。