退役选手 Challestend 的 CF 杂题题解
直角。
值得注意的是，本题解使用的记号可能与原题不同。
有些看题解看出来的思维题就不写代码了。
「CF558E」A Simple Task
给定一个长度为 $n$ 的仅包括小写英文字母的字符串。$m$ 次操作，每次给出一个区间要求升序或降序排序。输出最终得到的字符串。
$1\leqslant n\leqslant 10^5$，$0\leqslant m\leqslant 50000$。
显然我们可以将排好序的区间缩成一个点，然后维护一下每个点内部每个字母的出现次数和它的排序方式。一开始的时候可以认为是 $n$ 个点，每个点只包含一个字母且升序排序。
每次操作就把区间两边的点拆开，然后把整个操作区间并成一个大点。
时间复杂度 $O((n+m)|\Sigma|\log n)$，这题 $|\Sigma|$ 是常数 $26$ 所以实际上就是 $O((n+m)\log n)$。
然而拆点写不动 :(
写了大半天突然发现没考虑操作区间已经被包含在一整个点内部的情况于是果断放弃了。于是就没有代码实现了。
「CF451E」Devu and Flowers
给出 $n$ 个集合，第 $i$ 个集合有 $a_i$ 个元素。相同集合元素不可区分，不同集合元素可区分。从这里面选出 $m$ 个元素，问方案数，模 $998244353$。
$1\leqslant n\leqslant 20$，$0\leqslant m\leqslant 10^{14}$，$0\leqslant a_i\leqslant 10^{12}$。
首先我们发现 $m$ 和 $a_i$ 的范围都非常非常的大，也就是说 NTT 行不通了。
于是考虑容斥。转化为求
的解 $(x_1,x_2,\cdots,x_n)$ 的数量。
令 $F_k$ 表示恰好有 $k$ 个 $x_i\gt a_i$ 的方案数；$G_k$ 表示钦定 $k$ 个 $x_i\gt a_i$ 其他随意的方案数。那么
求出 $F_0$ 即可。
关于 $G_k$，注意到右边那个组合数因为 $n$ 很小，算一次只需要 $O(n)$。那么 $O(2^n)$ 暴力枚举左边的子序列就好。总时间复杂度 $O(n2^n)$。
我是绝对不会说我算减法忘了 +mod 结果 WA 了一发的（
当然我更不会说我因为每次求组合数 $O(n\log\text{mod})$ 暴力算阶乘逆元结果 TLE 了一发的（
功 力 尽 失
不会吧为什么 $O(n2^n)$ 和 $O(n2^n\log\text{mod})$ 差得这么多啊。
「CF1188B」Count Pairs
给定一个长度为 $n$ 的序列 $a$ 和常数 $p,k$。保证 $a_i$ 两两不同，且 $p$ 是质数。
求数对 $(u,v)$ 的数量，使得 $1\leqslant u\lt v\leqslant n$ 且 $(a_u+a_v)(a_u^2+a_v^2)\equiv k\pmod{p}$。
$2\leqslant n\leqslant 3\times 10^5$，$2\leqslant p\leqslant 10^9$，$0\leqslant k,a_i\lt p$。
太菜了没有思路于是被迫看题解。
考虑到 $a_i$ 两两不同，我们有
emmm 话说回来 $u,v$ 放在下标上是不是看不大清啊。
但是我觉得这种情况下 $u,v$ 两个字母算是最合适的了。所以说就这样吧（光速逃
没有代码实现。
「CF383D」Antimatter
给定一个长度为 $n$ 的序列 $a$。每次操作可以选定一个区间 $[l,r]$，将区间内每个数染成红色或者黑色（不可以不染色），如果红数黑数分别求和后结果相等，那么这次操作是合法的。求合法操作数量，模 $10^9+7$。两次操作不同当且仅当选定区间不同或者区间内至少一个数颜色不同。
$1\leqslant n,a_i\leqslant 1000$，$\sum a_i\leqslant 10000$。
太菜了没有思路于是被迫看题解。
令 $w=\sum_{i=1}^{n}a_i$。
首先我们有一个简单粗暴的背包搞法。令 $f(i,j,S)$ 表示在 $[i,j]$ 内选出若干个数加起来等于 $S$ 的方案数，那么这个显然可以 $O(n^2w)$ 搞出来。那么答案就是
但是这不够，我们需要优化。
考虑分治。设当前分治到 $[L,R]$，令 $m=\left\lfloor\frac{L+R}{2}\right\rfloor$，我们需要处理出左端点在 $[L,m]$ 上且右端点在 $(m,R]$ 上的所有区间的贡献。这里一个区间的贡献指的是一次操作选定这个区间后染色的方案数。
考虑任意选取 $x_1\in[L,m],x_2\in(m,R]$，令 $T_1=\sum_{i=x_1}^{m}a_i,T_2=\sum_{i=m+1}^{x_2}a_i$。设有一种操作，$[x_1,m]$ 上黑色数字之和为 $S_1$，$(m,x_2]$ 上黑色数字之和为 $S_2$。那么这次操作合法当且仅当
即
则 $[L,R]$ 上跨中点区间的贡献之和为
虽然这个式子像这样写出来很吓人，但实际上只要稍微发挥一下人类智慧我们就可以将其优化到 $O(w(R-L))$。具体方法读者可自行撕烤。
那么总时间复杂度 $O(nw\log n)$。
本来不想写的不过想了想还是写一下吧。
下了体育课就去写。
「CF1451E2」Bitwise Queries (Hard Version)
有一个长度为 $n$ 的序列 $a$，但是您不知道它长什么样。每次您可以指定 $1\leqslant u\lt v\leqslant n$，并得到 $a_u$ 和 $a_v$ 按位与 | 或 | 亦或的结果，这叫做一次查询。您最多只能进行 $n+1$ 次查询，然后您需要给出序列 $a$。
$4\leqslant n\leqslant 2^{16}$ 且 $n$ 是 $2$ 的幂，$0\leqslant a_i\lt n$。
以下，$\wedge$ 表示按位与，$\vee$ 表示按位或，$\oplus$ 表示按位异或。
首先我们需要对于 $i\gt 1$ 查询 $a_1\oplus a_i$，然后我们只需要知道 $a_1$ 的值即可还原出整个序列。
以下设 $t_i=a_1\oplus a_i$。显然 $t_1=0$。
若存在 $u\neq v$ 但是 $t_u=t_v$，这说明 $a_u=a_v$。那么我们查询 $a_u\wedge a_v$ 即可得到 $a_u$ 和 $a_v$，也就得到了 $a_1$。
否则，则 $t_i$ 两两不同，即 $a_i$ 两两不同。找到 $u$ 使得 $t_u=1$，查询 $a_1\wedge a_u$ 即可得到 $a_1$ 的二进制表示中除最低位以外的所有其他位。然后再找到 $v$ 使得 $t_v=2$，查询 $a_1\wedge a_v$ 即可得到 $a_1$ 的二进制表示的最低位。
注意到 $t_i\in[0,n)$ 且 $t_i\neq 0$，可以看出上述 $u,v$ 必定存在且唯一。
「CF1613E」Team Building
有 $n$ 个人，要从中选出恰好 $p$ 个人参加比赛以及恰好 $k$ 个人围观。第 $i$ 个人如果围观会产生 $a_i$ 的价值。参加比赛的话有 $p$ 个位置，第 $i$ 个人在第 $j$ 个位置上产生 $s_{i,j}$ 的价值。要求最大化价值和。
$2\leqslant n\leqslant 10^5$，$1\leqslant p\leqslant 7$，$1\leqslant k,p+k\leqslant n$，$1\leqslant a_i,s_{i,j}\leqslant 10^9$。
考虑到，如果我们已经确定好了要让哪些人参加比赛，那么剩下的人里面要去围观的一定是 $a_i$ 最大的那 $k$ 个人。
于是我们先将所有人按 $a_i$ 降序排序。令 $f_{i,S}$ 表示在前 $i$ 个人中选出一些人参加比赛并填满集合 $S$ 里的位置，然后其他人围观，这样能够得到的最大价值和。
同理，令 $g_{i,S}$ 表示在前 $i$ 个人中选出一些人参加比赛并填满集合 $S$ 里的位置，然后其他人闲着什么也不干，这样能够得到的最大价值和。
显然 $O(p2^pn)$ 可以处理出来。
然后答案就是 $\max_{i=|S|+k}(f_{i,S}+g_{n-i,U-S})$。其中 $U=\{1,2,\cdots,p\}$。
这题是我在学校的 ACM 实验室写出来的。一个下午一共写了两道题都和状压有关。下一题也是。
「CF547C」Mike and Foam
给定一个长度为 $n$ 的序列 $a$。您需要维护一个集合 $S$，初始为空。$m$ 次操作，每次给出一个下标 $x$，如果 $x\notin S$ 就将 $x$ 插入 $S$；否则就从 $S$ 中删除 $x$。每次操作后您需要给出下式的值
$1\leqslant n,m\leqslant 2\times 10^5$，$1\leqslant a_i\leqslant 5\times 10^5$。
以下令 $w=\max_{i=1}^{n}a_i$。
一开始我是这样想的：对于每个位置 $x$ 建立一个标号为 $x$ 的圆点；对于 $\leqslant w$ 的第 $i$ 个质数建立一个标号为 $i$ 的方点。每插入一个位置 $x$，如果第 $i$ 个质数能够整除 $a_x$，就在标号为 $x$ 的圆点和标号为 $i$ 的方点之间连一条边。
这样，$a_u\perp a_v$ 当且仅当标号为 $u$ 的圆点和标号为 $v$ 的圆点不连通。于是使用并查集维护。
但是这样的话不好删除，于是考虑线段树分治转化成只有插入没有删除。总时间复杂度 $O(m\log m\log(n+w))$。
但！是！……显然这种做法是假的。
考虑 $a=\{2,3,6\}$，我们发现按照上述建图方式我们会得到「这三个数两两不互质」这样的结论。但显然这是错的因为 $a_1\perp a_2$。
于是我们考虑容斥。令 $f_{x,v}$ 表示集合 $S$ 中有多少个下标 $y$ 满足 $(a_x,a_y)\geqslant v$。那么插入 $x$ 时产生的贡献就是
其中 $\mu(v)$ 表示莫比乌斯函数，要求 $|\mu(v)|=1$ 是因为我们只需要关注 $(a_x,a_y)$ 中有多少个不同的质因子，而并不需要知道这些质因子的次数分别是多少。
同时 $\gamma(v)$ 表示 $v$ 有多少个不同的质因子，$(-1)^{\gamma(v)-1}$ 就相当于是容斥系数。当然这个东西也可以用 $\mu(v)$ 来表示不过我觉得这样清晰一些。
然后值得注意的是上式计算的是有多少对 $(a_x,a_y)\gt 1$，最终答案实际上是 ${|S|\choose 2}$ 减去上式。
然后我们还需要维护一个 $c_v$ 表示集合 $S$ 中有多少个下标 $y$ 满足 $v|a_y$。
那么显然计算一次上式所需要的时间复杂度是 $O(2^{\gamma(a_x)})$。注意到
这意味着 $\gamma(v)\leqslant 7$。因此总时间复杂度 $O(2^7m)$。
虽然最慢的点跑了 $1871\text{ms}$ 不过还好吧。
「CF1404C」Fixed Point Removal
给定一个长度为 $n$ 的序列 $a$。每次可以删除一个满足 $a_i=i$ 的元素 $a_i$，且删除会使得元素的下标发生改变。$m$ 次询问，每次给出 $x,y$，将序列的最左侧 $x$ 个数和最右侧 $y$ 个数修改成 $n+1$，然后问最多进行多少次删除。询问相互独立即，上一次询问时被删除或被修改的元素会在下一次询问前复原。
$1\leqslant n,m\leqslant 3\times 10^5$，$1\leqslant a_i\leqslant n$。
被最新的多项式黑科技重工业干烂了继续来刷我的小水题。
每次询问相当于给出区间 $[l,r]$，然后只能删除这个区间内的元素。
考虑到对于 $a_i$，删除左侧的元素会使得其下标 $-1$，删除右侧的元素不会改变其下标。也就是说如果 $a_i\gt i$，那么其一定无法被删除。
如果 $a_i\leqslant i$，且能够在 $a_i$ 左侧进行至少 $i-a_i$ 次删除，那么 $a_i$ 一定能够被删除。每次贪心地删除最靠右的能够被删除的元素即可。
对于一次询问，显然其左端点越靠左，能够被删除的元素就会越多，且数量至少不会减少。即对于每个位置 $i$，存在一个 $f_i$，使得当询问区间包括 $i$ 时，若询问区间左端点 $\leqslant f_i$，那么 $a_i$ 能够被删除；否则 $a_i$ 不能被删除。
考虑二分求解 $f_i$。注意到当询问区间包括 $i$ 且左端点恰好为 $L$ 时，$a_i$ 能够被删除当且仅当区间 $[L,i)$ 上存在至少 $i-a_i$ 个 $k$ 满足 $f_k\geqslant L$。这部分可以使用主席树维护。总时间复杂度 $O(n\log^2 n)$。
「CF888G」Xor-MST
给定一个长度为 $n$ 的序列 $a$。构造一张无向完全图，其中点 $u$ 和点 $v$ 之间连一条边权为 $a_u\oplus a_v$ 的边。求最小生成树边权和。
$1\leqslant n\leqslant 2\times 10^5$，$0\leqslant a_i\lt 2^{30}$。
经典 Boruvka 算法练习题。
简单介绍一下这种 B 开头的最小生成树算法：
每次迭代对于每个点 $u$，找出当前与其不连通的所有点 $v$ 中 $(u,v)$ 边权最小的 $v$，然后连边 $(u,v)$。
这里有一个细节是，每次迭代的时候选出来的 $n$ 条边要按照边权从小到大连，否则可能会出现连了大边结果小边连不上了的情况。
不难看出每次迭代每个点所在的连通块大小至少翻倍，于是总时间复杂度 $O(f(n)\log n)$，其中 $f(n)$ 表示单次迭代的时间复杂度。
对于这道题，每次迭代需要对于每个点找出与其不连通的所有点 $v$ 中 $a_u\oplus a_v$ 最小的 $v$。这可以通过动态开点字典树实现，读者可自行撕烤。
于是 $f(n)=n\log a_i$，总时间复杂度 $(n\log n\log a_i)$。
然后调不出来了就这样吧。
「CF1528C」Trees of Tranquillity
给定两棵 $n$ 个节点的树 $S,T$，均以 $1$ 为根。构造一张无向图 $G$，其中 $u,v$ 两个点之间有边当且仅当它们在 $S$ 中是祖先后代关系且在 $T$ 中不是祖先后代关系。求 $G$ 的最大团大小。
$2\leqslant n\leqslant 3\times 10^5$。多组数据，$\sum n\leqslant 3\times 10^5$。
首先我们把这个题意翻译一下，就是让我们找出一些点且这些点中任意一对点在 $S$ 中是祖先后代关系且在 $T$ 中不是祖先后代关系。
显然这些点在 $S$ 中是从一条深度递增的链上抠下来的，因此考虑对 $S$ 中每一条深度递增且从根到叶子的路径计算贡献。
对于点 $u$，设 $[l_u,r_u]$ 为 $T$ 中 $u$ 的子树的 DFS 序区间，问题转化成在一些区间中选出尽可能多的区间互不相交。
考虑设 $f_k$ 表示当前选出的所有区间右端点最大值恰好为 $k$ 时最多能选出多少个区间；同理，$g_k$ 表示当前选出的所有区间左端点最小值恰好为 $k$ 时最多能选出多少个区间。那么显然如果我们一定要选区间 $[l_u,r_u]$，此时的答案为
使用线段树即可维护。总时间复杂度 $O(n\log n)$。
代码实现先等会爬会山先。
结果一连拖了好几天。