yaohaoyou

CF2245F Familiar?

感觉对性质的挖掘还是太深刻了。

首先套路将排列放在小根笛卡尔树中，手玩不难发现 $a_i$ 就是 $i$ 的左儿子的右链长度，考虑 dp。

令 $f_{l,r,i}$ 表示区间 $[l,r]$ 为根的子树中，包含当前节点的右链长度为 $i$ 的方案数。不难列出转移：

$f_{l,r,i}=\sum_{p\in [l,r]} \binom{r-l}{p-l}f_{l,p-1,}a_p\times f_{p+1,r,i-1}$

通过记录 $g_{l,r}=\sum f_{l,r,i}$ 可以做到 $\mathcal O(n^4)$。考虑优化。依旧发现区间 $[l,r]$ 的右链长度限制一定是由 $a_{r+1}$ 给来的，因为每次给限制都是将 $a_p$ 给到 $[l,p-1]$，而继续转移过程都是将限制放到 $[p+1,r]$，而又有性质 $\sum a_i\le n$。所以 $f_{l,r,i}$ 中的 $i\in[0,a_{r+1}]$，到这里就 $\mathcal O(n^3)$ 解决了 $a_i\neq -1$ 的情况。

对于 $a_i=-1$ 的位置，实际上不需要用到 $f$，只需要维护 $g$ 即可，转移也是 $\mathcal O(n^3)$ 的。注意空间限制，不能初始开满 $n^3$ 的 $f$，只开需要用到的部分，总空间为 $\mathcal O(n\sum a_i)=\mathcal O(n^2)$。

AT_arc227_f Erase and Raise

对于每次将一个区间 $(l,r)$ 的操作，可以通过构建折线图（类似括号匹配）来表示$\Large{\color{red}\Diamond}$，即将 $a_l$ 设置为向上的折线，$a_r$ 设置为向下的折线，最后剩下来的点用横线表示。题目所求的就是有多少种长度为 $n$ 的折线图满足不存在两个高度相同的横线。

对于一上一下的折线（即直接删除相邻两个数）没什么必要也不方便去重，可以钦定不存在这种情况，然后转化为长度 $\le n$ 且奇偶性和 $n$ 一样。令 $f_{i,j}$ 表示目前有 $i$ 个点，$j$ 个连续段的方案数，转移直接讨论是否合并连续段和是否存在横线即可，这部分不难。转移式中 $j$ 下降最快的方式是从 $f_{i,j} \to f_{i+2j+1,j-1}$，最后答案为 $\sum f_{i,1}$，所以 $j$ 的范围只需要考虑 $\mathcal O(\sqrt n)$ 即可。总复杂度为 $\mathcal O(n\sqrt n)$。

CF1799H Tree Cutting

最后树会被分成 $k+1$ 个连通块，其中每个连通块大小为 $a_i-a_{i-1}$。先 $k\gets k+1$，考虑将每个点染成 $[1,k]$ 中的一种颜色，思考什么时候能构造切割方式满足染色方案$\Large{\color{red}\Diamond}$。

对于割掉一条边 $(fa_x,x)$ 后进入 $fa_x$ 的情况，只需要保证 $x$ 子树中所有颜色都 $< col_{fa_x}$ 即可。对于进入 $x$ 的情况，需要让 $x$ 子树内的颜色有 $(col_{fa_x},k]$，因为后面的所有操作都只在 $x$ 子树中进行。

考虑完两种情况就可以 dp 了。令 $f_{u,s}$ 表示 $u$ 子树内有 $s$ 的颜色的方案数，先对儿子做类似卷积背包合并，然后考虑 $(u,fa_u)$ 是否断掉和往哪边走。复杂度为 $\mathcal O(n3^kpoly(k))$。

qoj18302 Remix

感觉像是比较典型的 ACM 手玩调整题。

因为整个序列的 $\max$ 是随操作不增的，所以先考虑最后一次操作时的 $\max$ 的性质。令 $a$ 中最大和次大值为 $x,y$，若操作了 $x$，最后能获得最小值 $mn$，则此时答案为 $y-mn$，若将对 $x$ 的操作都改成 $y$，则能获得 $mn' \le mn+x-y$ 的最小值，则此时的答案为 $x-mn'\ge y-mn$，所以一定可以调整到直到最后一步再操作 $x$。

接下来就是考虑去掉最大值后能凑出的最小值，本质上是对每个数分配 $-1/0/1$ 的系数后求和 $\ge 0$ 时的最小值（显然必要，充分证明由构造方式后面给出）。忽略掉 $0$ 的位置就是找两个子集 $S,T$ 求 $\min |sum(S)-sum(T)|$。比较神秘的是：共有 $2^n$ 种集合，构成至多 $\sum a_i+1$ 种 $sum(S)$，**因为抽屉原理，**当 $2^n>\sum a_i+1$ 时必然有两个不同子集和相同，这样就能构造出最小值 $=0$ $\Large{\color{red}\Diamond}$。解出来有 $n\ge 20$ 时必然能够造出 $0$，然后考虑构造方案。

除最后一次每次操作只需要操作 $2$ 个数即可，令 $sum(S)\ge sum(T)$，先令 $x=s_1$ 开始操作。只需要让 $S,T$ 内部的正负号相同，因为最后结果 $\ge 0$ 所以会自然正确。若 $x=\sum_{S'\sube S}sum(S')-\sum_{T'\sube T}sum(T')$ 则称为 $(+,-)$ 状态，否则为 $(-,+)$ 状态。为了保持构成 $x$ 时 $S,T$ 内部正负号相同，在 $(+,-)$ 时应和 $t_i$ 相减，$(-,+)$ 时和 $s_i$ 相减。总复杂度为 $\mathcal O(n+V)$。

AT_agc019_f [AGC019F] Yes or No

显然有策略当 $n>m$ 时猜YES，否则猜NO。由于YES和NO本质相同，考虑钦定 $n\ge m$。

当 $n\neq m$ 时，有 $\frac{n}{n+m}$ 的概率猜对，$(n,m) \to (n-1,m)$，$\frac{m}{n+m}$ 概率猜错，$(n,m)\to (n,m-1)$。猜对时会让差变小，猜错变大，所以若当前猜错会继续猜原来的答案。这样会已知进行到 $n=m$ 为止，此时会随便猜一个然后继续重复。考虑整个过程就是从 $(n,m)\to (x,x)$，并且过程中不经过 $n'=m'$，因为一直都是猜 $n$ 代表的，所以一定是猜对 $n-x$ 个。

总结一下刚刚的手玩得到的性质。从 $(n,m)$ 第一次到达 $(x,x)$ 时会猜对 $n-x$ 个（称为第一部分），然后有 $\frac 12$ 概率猜对（称为第二部分），然后继续到 $(x,x-1)$。从 $(n,m)$ 到 $(0,0)$ 过程中第一部分求和一定就等于 $n$，第二部分就是经过的 $n'=m'$ 的点的数量，所以答案就是 $\max(n,m)+\sum p(i,i)$，$p(i,i)=\frac{\binom{n-i+m-i}{n-i}\binom{2i}{i}}{\binom{n+m}n}$。

P7824 「RdOI R3」毒水

感觉挺好玩的，不知道有没有机会放联测里。

如果没有变异鼠是好做的，直接进行二进制分组，第 $i$ 次询问二进制中第 $i$ 位为 $1$ 的所有数，最后逐位确定毒药的每个二进制位即可。有变异鼠会导致可能这 $\log n$ 次询问有至多一个错误的，思考如何找出。

其实可以对这 $\log n$ 个继续做类似的事情$\Large{\color{red}\Diamond}$。令前面第 $i$ 次询问的集合为 $S_i$，现在第 $i$ 次询问考虑 $[0,\log n]$ 二进制中第 $i$ 位为 $1$ 的所有 $x$，询问 $\oplus S_x$，这样可以通过询问得到这些 $x$ 中变异或当前询问是变异的。若变异鼠在前 $\log n$ 次，则再询问完 $\log\log n$ 次后就可以确定是哪一个变异鼠，然后改正后就可以得到正确答案。但是还要考虑最后 $\log\log n$ 次是否有变异鼠，这里再增加一次询问最后 $\log\log n$ 个询问集合的异或。若判断出这两个部分中有变异鼠，则说明前 $\log n$ 个询问没有变异鼠，则可以直接求出答案。

总步数为 $\lceil\log_2n\rceil+\lceil\log_2\log_2n\rceil+1$，感觉其实是 sub4 卡得最紧。

【UNR #10】字符串

有较为神秘的观察：想比较 $s<rev(s)$ 时，只需要对于任意 $x\in[\lfloor\frac n2\rfloor,n]$,比较 $s[1,x]<s[n-x+1,n]$ 即可$\Large{\color{red}\Diamond}$。于是可以将询问 $[l,r]$ 的所有判定都进行二进制分组，在第 $i$ 组处理比较 $[l,l+2^i-1]$ 到 $[l,\min(r,l+2^{i+1}-2)]$，实际上就是比较 $s[l,l+2^i-1]$ 在集合 $S=\{x\in [2n-\min(l+2^{i+1}-2,r)+1,2n-l-2^i+2]|s[x,x+2^i-1]\}$ 中的排名。在 SA 时处理 $[x,x+2^i-1]$（不是整个后缀）的排名，从大往小扫描线，在线段树上进行单点修改和区间查询维护哈希值，可以做到 $\mathcal O((n+q)\log^2n)$。

实际上，将 $q$ 个询问拆成的 $q\log n$ 个询问中，只有最后一个区间是要和 $r$ 取 $\min$ 的，前面的都只和 $l$ 有关，所以预处理出所有左端点的 $n\log n$ 个询问，最后在求解时再拼上 $q$ 的最后一个区间即可$\Large{\color{red}\Diamond}$。共有 $\mathcal O(n\log n+q)$ 个询问，复杂度为 $\mathcal O(n\log^2n+q\log n)$。

P17286 「IXOI R2」Horizon Blue

数据范围和强制在线考虑操作分块，即每 $B$ 个询问就重构一次。

先考虑未修改前的询问 $[l,r]$ 如何做。将序列分块，预处理出每个点在块内的前驱后继 $pr,nx$，则这个点的贡献为 $a_i\times(i-\max(l-1,pr_i))\times (min(r+1,nx_i)-i)$，尝试将 $\max$ 和 $\min$ 拆开。实际上这个 $pr,nx$ 的性质很好，对于一个询问至多会有一个 $i$ 满足 $pr_i<l,nx_i>r$，这个就是区间最大值，剩下的至多满足其中一边$\Large{\color{red}\Diamond}$，下面以 $pr_i<l$ 为例。这样的点就是从 $l$ 走到 $r$ 的单调栈上的点，于是考虑预处理每个块内的单调栈，则从 $l$ 到这个块的单调栈一定就是这个块内单调栈的一个后缀，这直接在预处理时求贡献后缀和即可。为了防止二分多一个 $\log$，还需要预处理出上一个块的最大值在当前块的单调栈的位置。预处理和单次询问复杂度为 $\mathcal O(n)-\mathcal O(\sqrt n)$。令修改前对询问区间 $[l,r]$ 的答案为 $f(l,r)$。

上面是我自己想到的，但是好像需要 $\mathcal O(n)-\mathcal O(1)$ 才行，下面补充一下。做一下二维差分，令 $g(l,r,x,y)=\sum_{i\in[l,r]}\sum_{j\in[x,y]}\max_{k\in[i,j]}a_k$，$a_p=\max_{i=l}^r a_i$有

$f(l,r)={\color{red}g(l,p-1,l,p-1)}+{\color{green}g(p+1,r,p+1,r)}\\ ={\color{red}g(l,n,l,n)-g(p,n,p,n)-g(l,p-1,p,n)}+{\color{green}g(1,r,1,r)-g(1,p,1,p)-g(1,p,p+1,r)}\\$

$g(l,p-1,p,n)$ 的左端点对区间最大值一定没有贡献，只需要预处理在 $[p,n]$ 中每个数在多少个区间为最大值，另一边同理。同时预处理 $g(x,n,x,n),g(1,x,1,x)$ 就可以做到 $\mathcal O(n)-\mathcal O(1)$。

然后考虑修改后的点造成的贡献，令修改点 $x$ 的 $[l,r]=[\max(ql,pr_x+1),\min(qr,nx_x-1)]$，则区间 $[l,r]$ 的新贡献为 $-f(l,r)+f(l,x-1)+f(x+1,r)+a_x\times (x-l+1)\times (r-x+1)$，只需要对每个修改后的点都做一遍再加上 $f(l,r)$ 即可。复杂度为 $\mathcal O(qB+\frac{n^2}{B})$，当 $n,q$ 同阶时复杂度为 $\mathcal O(n\sqrt n)$。