UOJ上终于有了清华集训2016的题，喜闻乐见。于是乎，本人开始考后订正了。
这里是本人参加清华集训2016留下的各种遗憾：http://wronganswer.blog.uoj.ac/blog/2161
Day 1
T1：Alice和Bob又在玩游戏
考场情况
这题我的考场情况是这样的：
一眼作业题，我会 $O(n^2)$，很快码完60分。然后不是很会，之后思考的时候通过打表找规律，但没有发现任何有意义的性质，研究了几种构造性的方法但都是错误的。花费1h以上，没做出来。
怎么办？回到原来的式子，强行用个数据结构维护每个子树的所有转移？这样看来就是个Trie树合并？好像会做了。
写了1h，最后10min写完，连样例都没过，没时间调。
最后得分：60。就是开场提交的暴力分。
考后分析
这种博弈论问题属于我最经常掉坑的各类问题之一。显然可以想到一种基于Sprague-Grundy定理的暴力算法：用 $T_v$ 表示以 $v$ 为根的子树，记 $g(v)$ 为 $T_v$ 的Grundy值，转移时枚举选择的点 $x$，设 $T_v$ 中与 $x$ 到 $v$ 的路径相邻的点集为 $S_{v,x}$，那么选择 $x$ 转移到的状态Grundy值为 $\bigoplus_{u\in S_{v,x}}g(u)$。从而 $T_v$ 的所有操作转移到的状态的Grundy值集合 $G_v$ 为
$$G_v=\{\bigoplus_{u\in S_{v,x}}g(u)\lvert x\in T_v\}$$
可得 $g(v)=\mathrm{mex}G_v$。设根节点集合为 $R$，那么先手必胜当且仅当 $\bigoplus_{v\in R}g(v)>0$。关键在于如何快速计算所有的 $g(v)$。
这个问题直接做就行了。用 $C_v$ 表示 $v$ 的子节点集合，设 $x_v=\bigoplus_{u\in C_v}g(u)$。如果选择的点 $x=v$，那么转移到的状态Grundy值为 $x_v$。如果选择的点 $x\ne v$，那么 $x$ 就在以某个 $u\in C_v$ 为根的子树内。枚举这个 $u$，那么对于一个 $x\in C_u$，$x$ 到 $v$ 的路径分成 $x$ 到 $u$ 一段以及 $v$ 单点这两部分。和 $x$ 到 $u$ 这段路径相邻的点集 $S_{u,x}$ 的Grundy值为 $\bigoplus_{y\in S_{u,x}}g(y)$，和 $v$ 相邻的点集的Grundy值为 $x_v\oplus g(u)$，因此
$$G_v=\{x_v\}\cup\bigcup_{u\in C_v}\{\left(\bigoplus_{y\in S_{u,x}}g(y)\right)\oplus x_v\oplus g(u)\lvert x\in C_u\}=\{x_v\}\cup\bigcup_{u\in C_v}\{g'\oplus x_v\oplus g(u)\lvert g'\in G_u\}$$
同样地 $g(v)=\mathrm{mex}G_v$。暴力求出所有集合 $G_v$ 以得到所有 $g(v)$ 复杂度仍然是 $O(n^2)$ 的，可以用数据结构来维护集合。这里的操作是，对每个 $v$ 将所有子节点 $u\in C_v$ 的 $G_u$ 集合中所有数异或上一个数 $x_v\oplus g(u)$，然后求出这些集合的并，再加入一个数 $x_v$。把每个 $G_v$ 建成一个二进制Trie树，整体异或可以用标记实现，查询 $g(v)=\mathrm{mex}G_v$ 可以在树上二分以 $O(\log n)$ 的时间求出。合并集合时，用Trie树合并可以在 $O(n\log n)$ 的时间内完成所有合并。
这样总复杂度就是 $O(Tn\log n)$，得分100。代码实现并不复杂，主要在于要想清楚，注重思维。
总结
这题的得分情况是：现场大多数人AC了这道题，少数（不足20个）没有AC这题的人也有大多数是因为正解写挂导致的。我没能做出此题可以说是很不应该的。可以看出我平时有一大思维误区：做博弈论题不管三七二十一先打个表再说。对于这种没有太多性质、直接用数据结构就能维护的问题，打表并没有什么卵用，反而浪费了太多时间，用朴素的想法去考虑是必不可少的。
T3：数据交互
待填
Day 2
T1：如何优雅地求和
考场情况
首先观察题目，记 $g(n)=Q(f,n,x)$，如果 $f(k)=k$，那么 $g(n)=nx$。打表找规律以后猜想，如果 $f(k)$ 是别的多项式，$g(n)$ 仍然是 $n$ 的不超过 $m$ 次多项式。
那么只要求出 $g(0..m)$，然后线性插值一下就可以了。
然而，虽然插值可以做到 $O(m)$，但把 $n=0,1,\cdots,m$ 代入 $g(n)$ 需要 $O(m^2)$ 的时间，而且没想到如何优化。于是就写了 $O(m^2)$。
最后得分：95。
考后分析
事实上把 $n=0,1,\cdots,m$ 代入 $g(n)$ 就是算一个卷积：
$$g(n)=\sum_{k=0}^na_k{n\choose k}x^k(1-x)^{n-k}=\sum_{k=0}^n{a_kn!x^k(1-x)^{n-k}\over k!(n-k)!}=n!\sum_{k=0}^n{a_kx^k\over k!}\cdot{(1-x)^{n-k}\over(n-k)!}$$
令
$$A_i={a_ix^i\over i!}$$
$$B_i={(1-x)^i\over i!}$$
用FFT计算 $A$ 和 $B$ 卷积，即可 $O(m\log m)$ 求得 $n=0,1,\cdots,m$ 的 $g(n)$。这样就能通过100分了。
当然，这道题可以直接推导而不需要先猜想“$g(n)$ 是不超过 $m$ 次多项式”的结论。
根据组合数的意义可得
$$g(n)=\sum_{k_1=0}^1\sum_{k_2=0}^1\cdots\sum_{k_n=0}^1f(k_1+k_2+\cdots+k_n)x^{k_1+k_2+\cdots+k_n}(1-x)^{n-k_1-k_2-\cdots-k_n}$$
$$=\sum_{k_1=0}^1x^{k_1}(1-x)^{1-k_1}\sum_{k_2=0}^1x^{k_2}(1-x)^{1-k_2}\cdots\sum_{k_n=0}^1x^{k_n}(1-x)^{1-k_n}f(k_1+k_2+\cdots+k_n)$$
我们希望把 $f(k_1+k_2+\cdots+k_n)$ 表示出来。
为满足 $f(0)=a_0$，可以构造 $f(x)=a_0$。
在此基础上，为满足 $f(1)=a_1$，可以构造 $f(x)=a_0+(a_1-a_0)x$。
在此基础上，为满足 $f(2)=a_2$，可以构造 $f(x)=a_0+(a_1-a_0)x+{a_2-2a_1+a_0\over 2}x(x-1)$。
在此基础上，为满足 $f(3)=a_3$，可以构造 $f(x)=a_0+(a_1-a_0)x+{a_2-2a_1+a_0\over 2}x(x-1)+{a_3-3a_2+3a_1-a_0\over 6}x(x-1)(x-2)$。
……
由于 ${x\choose i}={(x-1)(x-2)\cdots(x-i+1)\over i!}$，考虑把 $f(x)$ 表示为
$$f(x)=\sum_{i=0}^mc_i{x\choose i}$$
则应满足
$$a_i=\sum_{j=0}^i{i\choose j}c_j$$
二项式反演（容斥）可得
$$c_i=\sum_{j=0}^i(-1)^{i-j}{i\choose j}a_j$$
假如已经求出了所有的 $c_i$，那么原式等于
$$\sum_{k_1=0}^1x^{k_1}(1-x)^{1-k_1}\sum_{k_2=0}^1x^{k_2}(1-x)^{1-k_2}\cdots\sum_{k_n=0}^1x^{k_n}(1-x)^{1-k_n}\sum_{i=0}^mc_ii!(k_1+k_2+\cdots+k_n)^\underline{i}$$
这里 $x^\underline{i}$ 表示下降幂 $x(x-1)(x-2)\cdots(x-i+1)$。考虑 $(k_1+k_2+\cdots+k_n)^\underline{i}$ 的展开式（仍然用下降幂表示），就是从 $i$ 个 $k_1+k_2+\cdots+k_n$ 中各取出一个 $k_j$ 组合起来，得到 $n^i$ 个项；在一项中，如果 $k_j$ 取了 $c$ 个，那么得到的项 $k_j$ 的幂次就是 $k_j^\underline{c}$。
显然，如果某一项包含因子 $k_j^\underline{2}$，那么无论 $k_j=0,1$，该项的值均为 $0$，故只考虑 $i$ 个因子互不相同的项。
这样的项显然有 $n^\underline{i}$ 个，用 $U_i$ 表示这些项的可重集合，$I(k_1,k_2,\cdots,k_n)$ 表示项 $I$ 代入 $k_1,k_2,\cdots,k_n$ 的结果，则原式等于
$$\sum_{k_1=0}^1x^{k_1}(1-x)^{1-k_1}\sum_{k_2=0}^1x^{k_2}(1-x)^{1-k_2}\cdots\sum_{k_n=0}^1x^{k_n}(1-x)^{1-k_n}\sum_{i=0}^mc_ii!\sum_{I\in U}I(k_1,k_2,\cdots,k_n)$$
$$=\sum_{i=0}^mc_ii!\sum_{I\in U_i}\sum_{k_1=0}^1x^{k_1}(1-x)^{1-k_1}\sum_{k_2=0}^1x^{k_2}(1-x)^{1-k_2}\cdots\sum_{k_n=0}^1x^{k_n}(1-x)^{1-k_n}I(k_1,k_2,\cdots,k_n)$$
每个 $I\in U_i$ 恰为 $i$ 个 $k_j$ 相乘得到，例如 $I=k_1k_2\cdots k_i$：
$$\sum_{k_1=0}^1x^{k_1}(1-x)^{1-k_1}\sum_{k_2=0}^1x^{k_2}(1-x)^{1-k_2}\cdots\sum_{k_n=0}^1x^{k_n}(1-x)^{1-k_n}k_1k_2\cdots k_i=\prod_{j=1}^ix\cdot\prod_{j=i+1}^n(1-x+x)=x^i$$
所以原式等于
$$\sum_{i=0}^mc_ii!n^\underline{i}x^i$$
因此只要计算出所有的 $c_i$ 就能得到上式的结果了。
不难发现 $c_i$ 也是卷积的形式：
$$c_i=\sum_{j=0}^i(-1)^{i-j}{i\choose j}a_j=i!\sum_{j=0}^i{a_j\over j!}\cdot{(-1)^{i-j}\over(i-j)!}$$
同样可以FFT优化，在 $O(m\log m)$ 时间内通过本题。
总结
这个模型挺基础的，这题现场有8个人AC，并且这题有不少类似的原题，需要熟练掌握。
当然考场上为了节省时间选择打 $O(m^2)$ 暴力也是可行的选择。
T2：工厂
待填
T3：连通子树
题目太丧，不打算填
Day 3
T1：石家庄的工人阶级队伍比较坚强
考场情况
这题我在考场上一开始写了个10分暴力并用矩阵快速幂优化到20分，然而这个分数太低了。
觉得这题很难做就去做后面的题，在我第2题钻研失败以后回来想这题时剩大概1h，为了发现性质，我把矩阵打出来看有没规律，发现矩阵类似循环矩阵。再想想，就发现了转移矩阵 $A$ 的 $t$ 次幂中，如果 $x\ominus y=z$（这里 $\ominus$ 表示三进制不进退位减法），则 $A^t_{x,y}=A^t_{z,0}$，因此只要计算矩阵的第一列即可。于是我把矩阵优化成只有一列的以后测了下过不了 $m=7$，于是只有35分。
继续观察，注意到矩阵里只有 $\frac{(m+1)(m+2)}{2}$ 个数，那么好像矩阵可以继续缩小？发现了当 $a$ 和 $b$ 中0的个数和1的个数分别相等时，$A^t_{a,0}=A^t_{b,0}$。于是矩阵里面只要记每种0的个数和1的个数的数即可。然而由于考场上时间不多没法细想，没想出这种矩阵怎么乘法……更何况缩完以后还要对每个 $0\le x < n$ 枚举1的个数 $c_1$、2的个数 $c_2$，统计把 $x$ 中 $c_1$ 个位置减1，$c_2$ 个位置减2（都是不进退位的）得到的数 $y$ 的 $f_{0,y}$ 之和，也没有什么思路。
之后的思路卡在了 $\frac{(m+1)(m+2)}{2}$ 的矩阵的做法上，没有进展。考试就结束了。
最后得分：35。
考后分析
以下是我考后继续研究这个问题的过程：
记矩阵 $A_{x,y}=b_{W(x,y),L(x,y)}$，那么 $A^t_{x,y}$ 表示 $f_{t,x}$ 中 $f_{0,y}$ 的系数，即
$$\begin{pmatrix}f_{t,0}\\\cdots\\f_{t,n-1}\end{pmatrix}=A^t\begin{pmatrix}f_{0,0}\\\cdots\\f_{0,n-1}\end{pmatrix}$$
矩阵 $A$ 的乘法显然要优化。用 $\ominus$ 表示三进制不进退位减法，$\mathrm{count}_1(x)$ 和 $\mathrm{count}_2(x)$ 表示 $x$ 的三进制表示中1和2的个数，显然 $A$ 有两个性质：（1）对任意 $k$，$A_{x,y}=A_{x\ominus k,y\ominus k}$；（2）若 $\mathrm{count}_1(x)=\mathrm{count}_1(y),\mathrm{count}_2(x)=\mathrm{count}_2(y)$，则 $A_{x,0}=A_{y,0}$。
用数学归纳法还可以证明 $A^t$ 也是满足这两个性质的：
$$A^t_{x,y}=\sum_{z=0}^{n-1}A^{t-1}_{x,z}A_{z,y}=\sum_{z=0}^{n-1}A^{t-1}_{x\ominus k,z}A_{z,y\ominus k}=A^t_{x\ominus k,y\ominus k}$$
设函数 $\theta(x)$ 将 $\overline{x_0x_1\cdots x_{m-1}}$ 变换为 $\overline{x_{p_0}x_{p_1}\cdots x_{p_{m-1}}}$，$\{p_i\}$ 为 $0,1,\cdots,m-1$ 的一个排列，则
$$A^t_{x,0}=\sum_{z=0}^{n-1}A^{t-1}_{x\ominus z,0}A_{z,0}=\sum_{z=0}^{n-1}A^{t-1}_{\theta(x)\ominus z,0}A_{z,0}=A^t_{\theta(x),0}$$
而如果 $\mathrm{count}_1(x)=\mathrm{count}_1(y),\mathrm{count}_2(x)=\mathrm{count}_2(y)$，则一定存在排列 $\{p_i\}$ 满足 $\theta(x)=y$。
因此只需记 $A'^t_{c_1,c_2}=A^t_{x,0}$，其中 $\mathrm{count}_1(x)=c_1,\mathrm{count}_2(x)=c_2$。$A'^t$ 的空间只有 $\frac{(m+1)(m+2)}{2}$，看起来非常不错的样子。然而——该怎么求 $A'^t$？
好的那我就继续推。$A^t_{x,0}=\sum_{z=0}^{n-1}A^i_{x\ominus z,0}A^{t-i}_{z,0}$，要对 $O(m^2)$ 个 $x$ 计算这个式子，这样可以由 $A^i$ 在 $O(3^mm^2)$ 时间内推出 $A^{i+1}$ 或 $A^{2i}$，但还是很慢……等等，既然 $A_{x,0}$ 只和 $\mathrm{count}_1(x),\mathrm{count}_2(x)$ 有关，那能否不枚举 $z$ 而枚举 $\mathrm{count}_1(z)$ 和 $\mathrm{count}_2(z)$？
接着我推了下……失败了……因为我并不知道 $x\ominus z$ 中各个数位个数= =不过好像还是可以做的？枚举 $x$ 的0,1,2每一种数位在 $z$ 中0,1的个数（枚举两种数的个数可以确定剩下一种），这样 $z$ 和 $x\ominus z$ 中各种数位个数都确定了，满足这个条件的 $z$ 的个数是若干个组合数的积（写起来比较复杂），加的时候乘上这个积作为系数即可。现在的复杂度是啥……$O(m^2)$ 种 $c_0,c_1$ 以及 $O(m^6)$ 的枚举？$O(m^8)$？这其实就是方程
$$c_{00}+c_{01}+c_{02}+c_{10}+c_{11}+c_{12}+c_{20}+c_{21}+c_{22}=m$$
的非负整数解组数，即 $C_{m+8}^8\le C_{20}^8=125970$，再乘一个 $\log_2 t$ 也挺快的嘛……
现在已经求出了 $A'^t$，也就得到了 $A^t$ 矩阵第一列。记 $g_x=A^t_{x,0}$，那么 $f_{t,x}=\sum_{y=0}^{n-1}f_{0,y}g_{x\ominus y}$。这是啥？就是一个类似卷积的东西？记 $\oplus$ 为三进制不进位加法，那么需要做的事情就是对所有的 $x,y\in\{0,1,\cdots,n-1\}$，把 $f_{t,x\oplus y}$ 加上 $f_{0,x}g_y$。
这一步做完，这题就做完了。可是……
卷积……FFT？这数据范围，$3^{12}=531441$ 不像能FFT？异或卷积……FWT？好像以前写过二进制版本的，可是三进制的并不会啊，再说FWT好久没写我也有点忘了QAQ
$g$ 序列有性质吗？似乎有很多相等的数。然后想了想01（二进制）多项式卷积也得FFT，就觉得可能唯一的做法就是FWT了。于是就开始脑（hui）补（yi）FWT怎么写，一开始想先把两个式子做一个什么变换，然后乘起来最后变换回去，问题是想了半天还是不会那个变换。
接着就弃疗去想分治乘法了。
用 $f_0g$ 表示序列 $f_0,g$ 三进制异或卷积结果，即 $f_t=f_0g$。把 $f_0,g,f_t$ 序列都分成 $[0,3^{m-1}),[3^{m-1},2\cdot 3^{m-1}),[2\cdot 3^{m-1},3^m)$ 三段，记为 $A_0,A_1,A_2$、$B_0,B_1,B_2$、$T_0,T_1,T_2$。那么就可以看出（说明：序列的 $+,-$ 表示逐位对应相加/减，$kA$ 表示序列 $A$ 逐位乘 $k$ 得到的序列）：
$$T_0=A_0B_0+A_1B_2+A_2B_1$$
$$T_1=A_0B_1+A_1B_0+A_2B_2$$
$$T_2=A_0B_2+A_1B_1+A_2B_0$$
要优化复杂度显然不能每个 $A_iB_j$ 暴力递归算。回忆了下二进制的做法好像是构造了 $C_0=(A_0+A_1)(B_0+B_1)$ 和 $C_1=(A_0-A_1)(B_0-B_1)$，然后用 $C_0$ 和 $C_1$ 线性组合表示出 $T_0,T_1$。所以？三进制的话，是不是也要构造类似的式子？
经过了很久的尝试，发现好像怎么配系数都配不出来，想放弃的时候，想到如果构造 $(A_0+xA_1+yA_2)(B_0+xB_1+yB_2)$ 的话，那么 $A_0B_0,A_1B_2,A_2B_1$ 的系数分别是 $1,xy,xy$，$A_0B_1,A_1B_0,A_2B_2$ 的系数分别是 $x,x,y^2$，$A_0B_2,A_1B_1,A_2B_0$ 的系数分别是 $y,x^2,y$（容易证明，序列的异或卷积满足分配律 $A(B+C)=AB+AC$）。如果要使得 $T_0,T_1,T_2$ 每一类三个系数相等，就要满足 $xy=1$，$x=y^2$，$y=x^2$。所以？$x^3=1$，想到了什么？三次单位根？
好像是可以的诶，如果记三个三次单位根为 $1,\omega,\omega^2$，取 $x=\omega$，就会发现 $y=x^2$ 是另一个根 $\omega^2$，那我就三个式子带入三个单位根吧：
$$C_i=(A_0+\omega^iA_1+\omega^{2i}A_2)(B_0+\omega^iB_1+\omega^{2i}B_2)$$
那么如果计算出了 $C_0,C_1,C_2$，该怎么还原出 $T_0,T_1,T_2$ 呢？由于 $C_0=T_0+T_1+T_2$，$C_1=T_0+\omega T_1+\omega^2 T_2$，$C_2=T_0+\omega^2 T_1+\omega T_2$，设 $T_i=k_{i,0}C_0+k_{i,1}C_1+k_{i,2}C_2$，则
$$\begin{pmatrix}k_{0,0}&k_{0,1}&k_{0,2}\\k_{1,0}&k_{1,1}&k_{1,2}\\k_{2,0}&k_{2,1}&k_{2,2}\end{pmatrix}\begin{pmatrix}1&1&1\\1&\omega&\omega^2\\1&\omega^2&\omega\end{pmatrix}=\mathbf{E}_3$$
一个喜闻乐见的结论是，因为 $\omega^3=1$ 且 $1+\omega+\omega^2=0$，所以
$$\begin{pmatrix}1&1&1\\1&\omega^2&\omega\\1&\omega&\omega^2\end{pmatrix}\begin{pmatrix}1&1&1\\1&\omega&\omega^2\\1&\omega^2&\omega\end{pmatrix}=3\mathbf{E}_3$$
好的问题马上解决了，已经可以还原出 $T_i$ 了：
$$T_i=\frac{1}{3}(C_0+\omega^{2i}C_1+\omega^iC_2)$$
这样就能比较快地计算两个长度为 $3^m$ 的序列 $A,B$ 的三进制异或卷积了：把两个序列均等分成三段 $A_0,A_1,A_2$ 和 $B_0,B_1,B_2$，构造并递归计算 $C_0,C_1,C_2$，然后算出 $T_0,T_1,T_2$，最后 $T_0,T_1,T_2$ 连接得到的结果就是 $AB$。复杂度的话，$T(m)=3T(m-1)+3^m$，从而 $T(m)=3^mm$。这个复杂度完全可以接受。
问题是三次单位根是复数意义下的，模 $p$ 意义下要怎么办？一种简单粗暴的做法是把每个数表示为 $a+b\mathrm{i}$ 的形式，$a,b$ 是实数，然后就会发现实数也不一定能在模意义下表示，这就很尴尬了= =b
回头看下乘法涉及的 $\omega$ 是个啥，其实是 $-\frac{1}{2}+\frac{\sqrt 3}{2}\mathrm{i}$。猜想运算过程中 $a$ 和 $\frac{b}{\sqrt 3}$ 都是有理数，因此换一种表示方法，不用 $a+b\mathrm{i}$，而用 $a+b\sqrt 3\mathrm{i}$ 如何？易证形如 $a+b\sqrt 3\mathrm{i},a,b\in\mathbf{Q}$ 的数对于加法和乘法都是封闭的：
$$(a+b\sqrt 3\mathrm{i})+(c+d\sqrt 3\mathrm{i})=(a+c)+(b+d)\sqrt 3\mathrm{i}$$
$$(a+b\sqrt 3\mathrm{i})(c+d\sqrt 3\mathrm{i})=(ac-3bd)+(ad+bc)\sqrt 3\mathrm{i}$$
值得一提的是不仅需要乘法，还需要支持除以2和除以3的操作。看到题目对 $p$ 有一个奇葩的保证了没？不存在 $x,y\in\mathbf{N^ * }$ 使得 $\frac{1}{x}+\frac{1}{y}=\frac{3}{p}$，那么 $2$ 和 $3$ 都不整除 $p$。因为：
（1）如果 $2$ 整除 $p$，那么令 $x=\frac{1}{2}p,y=p$，则 $\frac{1}{x}+\frac{1}{y}=\frac{3}{p}$；
（2）如果 $3$ 整除 $p$，那么令 $x=y=\frac{2}{3}p$，则 $\frac{1}{x}+\frac{1}{y}=\frac{3}{p}$。
这样 $2$ 和 $3$ 模 $p$ 都有逆元，就能完成模意义下的除以 $2$ 和除以 $3$ 操作了。
于是，把异或卷积涉及到的元素都改成 $a+b\sqrt 3\mathrm{i},a,b\in\mathbf{Q}$ 的形式，$a,b$ 均在模 $p$ 意义下，就做完了。
不过常数比较大……我一开始写完极限数据 $2\texttt{s}$ 跑不过去……然后immortalCO帮我优化了一发常数，把递归过程的乘 $\frac{1}{3}$ 操作去掉，改成输出时乘 $\frac{1}{3^m}$，于是成功在UOJ垫底了。
http://uoj.ac/submission/130962
通过本人打表找规律发现，题目对 $p$ 的保证等价于 $p$ 的质因数分解式 $p=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$ 中，所有的 $p_i\equiv 1\pmod 6,i=1,2,\cdots,k$。并且，异或卷积中涉及到的 $\omega$ 实际上要满足的两个条件是 $\omega^3=1$ 和 $1+\omega+\omega^2=0$，如果用具有相同性质的模 $p$ 意义下的 $x$ 代替 $\omega$，算法仍然是正确的，继续打表找规律发现，所有满足这个条件的 $p$ 都存在整数 $x$ 使得 $x^3\equiv 1\pmod p$ 且 $1+x+x^2\equiv 0\pmod p$。
如果能找出这个 $x$，用它代替 $\omega$，那么就不需要把数表示成 $a+b\sqrt 3\mathrm{i}$ 的形式了！问题来了，这个 $x$ 怎么找？
……我好像知道质数怎么找诶？如果 $p$ 是质数（从而 $p\ge 7$），那么找出 $p$ 的原根 $g$，因为 $p\equiv 1\pmod 6$，所以取 $x=g^\frac{p-1}{3}$ 就能满足条件了，这是由于 $x^3\equiv g^{p-1}\equiv 1\pmod p$ 且 $1+x+x^2\equiv\frac{(1+x+x^2)x-(1+x+x^2)}{x-1}\equiv 0$。可是，如果 $p$ 是合数，连原根都不一定有了，不会了啊……
于是就去看题解= =
题解的做法是：先将 $p$ 质因数分解 $p=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$，然后对每个 $p_i^{c_i}$ 求出三次单位根 $x_i$，则满足 $\forall i=1,2,\cdots,k,x\equiv x_i\pmod p_i$ 的 $x$ 就是 $p$ 的三次单位根，用中国剩余定理合并即可。每个 $p_i^{c_i}$ 可以用之前的方法求原根解决。然后由于本人是SB，不知道合数的原根定义是啥，看了题解才明白只要把之前的 $p-1$ 换成 $\phi(p)$ 就能支持形如 $p_i^{c_i}$ 的模数了。经过实测验证发现这种做法确实能求出满足要求的 $p$ 的三次单位根。
OK，用这个 $x$ 代替原来的复数，交到UOJ，运行时间立刻缩短了。
http://uoj.ac/submission/131266
总结
这题考场上有多人得到85分以上的分数，因此并不像本人看到题时所想象的那样不可做。当然，从考后分析来看，即使考场上给本人更多的时间，也不太可能得到多于40的分数，主要是由于本人在FWT方面的知识缺陷导致的。
这题只有35分只能说我实力不足吧。从考场上这题得分情况来看，FWT已经是十分普及的了，如果不会FWT就很不应该了。不得不说这题是一道好题，涉及代数和数论的多个知识点综合应用，同时我也通过这题发现了自己的知识缺陷，收获还是不小的。
更多问题
这题可以说是我折腾了非常久的一道题。不过还是有一些问题有待思考：
1、对 $p$ 求三次单位根的做法依赖的一些性质我不太会证明。如何证明形如 $p^c$（$p$ 为质数，$p\equiv 1\pmod 6$，$c\in\mathbf{N^ * }$）的数用这种方法都能求出满足 $x^3\equiv 1\pmod{p^c}$ 且 $1+x+x^2\equiv 0\pmod{p^c}$ 的 $x$？另外，$p$ 的所有质因子模 $6$ 余 $1$ 是否为不存在 $x,y\in\mathbf{N^ * }$ 使 $\frac{1}{x}+\frac{1}{y}=\frac{3}{p}$ 的充分必要条件？为什么？
2、仔细看FWT的实现过程，发现和FFT有极其相似的地方，能否说明FWT是一种特殊的FFT？这种算法能否扩展到更复杂的情况（如多维数组的卷积）？
T2：你的生命已如风中残烛
考场情况
考场上，我首先写了个 $O(m!\cdot m)$ 的暴力，写完以后出了几组数据找规律，但除了发现当 $n=2$ 时答案为 $w_0+w_1$ 以外，没发现任何别的规律。（为了方便起见，之后的叙述不考虑 $0$ 的排列方案数，即答案都被除以了 $(m-n)!$）
然后开始推性质。之前做过类似这种 $n$ 远小于 $m$ 的排列计数问题有一种思想：先枚举 $n$ 个元素的排列，然后枚举有多少种将排列放置在序列中的方案。于是我就这么考虑：将长度为 $m$ 的序列位置依次标号为 $0,1,\cdots,m-1$，序列枚举的排列为 $1,2,\cdots,n$，其中元素依次为 $w_0,w_1,\cdots,w_{n-1}$，若 $p_i$ 为 $i$ 放置的位置，那么需要满足的条件是对任意 $i$，$p_i\le w_1+w_2+\cdots+w_{i-1}$，否则前 $p_i$ 个位置的元素和小于 $p_i$，不满足要求。
记 $f(i,j)$ 为已经确定了 $0,1,\cdots,i$ 这些元素的位置，将剩余元素排在 $S_j=w_0+w_1+\cdots+w_{j-1}$ 之后位置的方案数。转移时枚举 $(S_j,S_{j+1}]$ 这一段放置数的个数 $k$，则有
$$f(i,j)=\begin{cases}\sum_{k=0}^{n-i-1}C_{w_j}^kf(i+k,j+1),&j\le i < n-1\\1,&i=n-1\\0,&\mathrm{otherwise}\end{cases}$$
答案是所有排列的 $f(0,0)$ 和，这样复杂度是 $O(n!\cdot n^3)$，有30分。可是枚举排列太暴力了，我试下能不能改成状压DP。
于是就设计出了这样一种状压DP：记 $U=\{0,1,\cdots,n-1\}$，$f(S,T)$ 为已经确定集合 $S$ 中元素的位置，将剩余元素排在 $\sum_{i\in T}w_i$ 之后位置的方案数，其中 $T\subseteq S\subseteq U$，转移时枚举 $(\sum_{i\in T}w_i,\sum_{i\in S}w_i]$ 这一段放置的位置集合 $S'$，则有
$$f(S,T)=\begin{cases}\sum_{S'\subseteq U-S,S'\ne\varnothing}C_{\sum_{i\in S-T}w_i}^{|S|}f(S+S',S),&S\ne U\\1,&S=U\end{cases}$$
复杂度 $O(4^n)$，遗憾的是这样还是只有30分。
接着优化……？能否状态里面只记一个集合？然后不管怎么设计状态都有后效性，好惨。或者……如果我记一下上一段 $w$ 的和呢？复杂度好像更差。然后掉进优化DP的坑一直出不来= =
后面再想能否从小的 $n$ 开始考虑问题，$n=3$ 答案是啥？用那种枚举排列的方法好像可以证明它是关于 $w_0,w_1,w_2$ 的多项式，不过貌似有好多项。暴力DP出这个多项式然后代入？接着再次想错，认为 $n=15$ 时的项数为 $C_{28}^{14}$，复杂度不能接受。
因此花了这么多时间没有半点进展。交了 $O(4^n)$ 状压DP上去。
最后得分：30。
考后分析
实际上由 $O(n!n^3)$ 枚举排列DP推出的状压DP完全可以优化到 $O(2^nn^3)$。
我在考完以后听说不少人这题写了50分的状压DP，同样是状压，为何别人能得50而我只能得30？一定是我复杂度太糟糕了。于是考后我又继续思考了很长时间的优化，然而还是没想出哪怕是优化到 $O(3^n)$ 的做法。看了题解发现复杂度居然不是 $O(3^n)$ 而是 $O(2^nn^3)$，然而并不是很能理解题解中的50分做法，只好自己再研究一段时间。
后来研究了一下午= =发现优化其实挺简单的。
首先如果已经确定了 $n$ 个元素的排列顺序 $0,1,\cdots,n-1$，记 $S_i=\sum_{j=0}^{i-1}w_j$，则满足“对于所有的 $i$，位置在 $(S_i,S_{i+1}]$ 内的元素个数为 $c_i$”的排列数为
$$\prod_{i=0}^{n-2}C_{w_i}^{c_i}$$
原先的做法，枚举排列之后的DP，是直接枚举将多少个数加入序列，也就是当加入 $(S_j,S_{j+1}]$ 的元素确定以后才乘上 $C_{w_j}^{c_j}$。这个做法扩展到集合DP就不得不枚举子集，但是我们可以做一点调整：在 $j$ 加入序列的时候就确定 $(S_j,S_{j+1}]$ 中的元素个数 $c_j$ 并乘上 $C_{w_j}^{c_j}$，这就相当于一边加入元素，一边确定后面部分元素的位置。DP状态需要加入一维表示还有几个数的位置已确定。
记 $f(S,k)$ 为已经确定序列的 $n$ 个元素 $U=\{0,1,\cdots,n-1\}$ 中的前 $|S|$ 个元素集合为 $S$，且已经确定了前 $|S|+k$ 个元素的位置，剩下元素都在 $(\sum_{i\in S}w_i,m)$ 内的位置方案数，其中 $S\subseteq U$。转移时，如果 $k>0$，枚举第 $|S|+1$ 个元素 $i$ 以及 $(\sum_{x\in S}w_x,\sum_{x\in S}w_x+w_i]$ 这一段内的元素个数 $j$，那么就能决定 $(\sum_{x\in S}w_x,\sum_{x\in S}w_x+w_i]$ 这一段的 $j$ 个元素的放置方案数，为 $C_{w_i}^j$；如果 $k=0$，那么无法继续放置元素，可以得到
$$f(S,k)=\begin{cases}\sum_{i\in U-S}\sum_{j=0}^{n-|S|-k}C_{w_i}^jf(S+\{i\},k+j-1),&S\ne U,k>0\\1,&S=U\\0,&\mathrm{otherwise}\end{cases}$$
答案为 $f(\varnothing,1)$（显然，一开始只确定了 $[0,0]$ 内放了一个元素）。复杂度为 $O(2^nn^3)$，可以得50分。
事实上，问题可以从另外一种不同的角度来分析。
我之前在考场上发现答案是关于 $w_0,w_1,\cdots,w_{n-1}$ 的 $n$ 次多项式，这显然是正确的，可以从上述DP的分析中看出来：枚举每一段内的元素个数之后，方案数是若干个组合数的积，而组合数 $C_{w_i}^{c_i}$ 是关于 $w_i$ 的 $c_i$ 次多项式，而多项式的乘法和加法结果也是多项式。问题在于这个多项式的项可以包含 $w_0,w_1,\cdots,w_{n-1}$ 的任何次幂，所以项数是指数级的。
暴力算这个多项式 $n=15$ 都过不了，但问题并不是我所想象的那样毫无办法。
一方面，如果暴力DP求多项式的时候不去展开多项式而是保留组合数的形式，不需要多项式乘多项式，问题会方便很多。这样的多项式每一项实际上形如 $k\prod_{i=0}^{n-1}C_{w_i}^{c_i}$，其中 $\sum_{i=0}^{n-1}c_i=n-1$。
当然这样的话项数是 $\sum_{i=0}^{n-1}(c_i+1)=2n-1$ 的非负整数解个数，即 $C_{2n-2}^{n-1}$，仍然不能接受哪怕是 $n=15$ 的数据。
不过再稍微思考一下就会发现有一个强有力的优化（我怎么这么SB没有想到这一步就直接弃疗了呢，虽然好像就算想到了也没时间写了）：不妨设答案中，$\prod_{i=0}^{n-1}C_{w_i}^{c_i}$ 这一项的系数为 $k_{c_0,c_1,\cdots,c_{n-1}}$，若 $[c_0,c_1,\cdots,c_{n-1}]=[c_0',c_1',\cdots,c_{n-1}']$，则 $k_{c_0,c_1,\cdots,c_{n-1}}=k_{c_0',c_1',\cdots,c_{n-1}'}$，这里 $[]$ 符号表示可重集。举个例子，$C_{w_0}^1C_{w_1}^2$ 和 $C_{w_0}^2C_{w_1}^1$ 的系数是相同的。
这个优化意味着什么？只需要计算所有和小于 $n$ 的正整数可重集对应项的系数了！打个表，看看和小于 $40$ 的正整数可重集有多少个……只有 $177970$ 个！
是不是非常愉快呢，现在咱们考虑下怎么算系数。这里沿用朴素的“枚举排列DP求方案数”（30分做法）的思路。
记 $\mathrm{Perm}(U)$ 为 $U=\{0,1,\cdots,n-1\}$ 的全排列。先枚举这些元素的排列，记当前枚举到的排列为 $< p_0,p_1,\cdots,p_{n-1} >$。先把我考场上推的30分式子拉下来：
$$f(i,j)=\begin{cases}\sum_{k=0}^{n-i-1}C_{w_{p_j}}^kf(i+k,j+1),&j\le i < n-1\\1,&i=n-1\\0,&\mathrm{otherwise}\end{cases}$$
要知道 $f(0,0)$ 中项 $I$ 的系数（$I$ 就是那个一坨组合数乘起来的玩意），用 $I_0$ 表示单位元（即 $1$），可以这样做：记 $f'(i,j,I)$ 表示 $f(i,j)$ 中 $I$ 的系数，则
$$f'(i,j,I)=\begin{cases}\sum_{k=0}^{n-i-1}f'(i+k,j+1,\frac{I}{C_{w_{p_j}}^k}),&j\le i < n-1,C_{w_{p_j}}^k|I\\1,&i=n-1,I=I_0\\0,&\mathrm{otherwise}\end{cases}$$
不难发现，上面的 $i$ 这一维是没有用的。记 $I$ 的次数为 $|I|$（例如当 $I$ 为 $C_{w_0}^2C_{w_1}^1$ 时，$|I|=3$），那么 $i=n-|I|-1$，因此可以写成这样：
$$f'(I,j)=\begin{cases}\sum_{k=0}^{|I|}f'(\frac{I}{C_{w_{p_j}}^k},j+1),&j\le n-|I|-1 < n-1,C_{w_{p_j}}^k|I\\1,&I=I_0\\0,&\mathrm{otherwise}\end{cases}$$
用 $F$ 表示组合数项的集合，$I(p_0,\cdots,p_{n-1})$ 表示项 $I$ 中用 $w_{p_0},\cdots,w_{p_{n-1}}$ 代入 $w_0,\cdots,w_{n-1}$ 得到的结果，那么答案就是
$$\sum_{< p_0,\cdots,p_{n-1} >\in\mathrm{Perm}(U)}\sum_{I\in F}f'(I,0)I(p_0,\cdots,p_{n-1})=\sum_{I\in F}f'(I,0)\sum_{< p_0,\cdots,p_{n-1} >\in\mathrm{Perm}(U)}I(p_0,\cdots,p_{n-1})$$
根据前文提到的优化，只需对每个可重集 $J$ 求出系数集为 $J$ 的项 $I$ 的个数和这样的项的 $f'(I,0)$ 的乘积——不妨下文直接记 $f(J)$ 为系数集为 $J$ 的项 $I$ 的个数和这种项的 $f'(I,0)$ 值的积（我知道这里 $f$ 重名了）。只需预处理所有和小于 $n$ 的正整数可重集构成的集合 $S$，将 $S$ 中元素从 $0$ 到 $|S|-1$ 标号，然后对每个 $J\in S$ 和正整数 $k < n$ 预处理出 $J+\{k\}$ 在 $S$ 中的标号，再通过将上述DP改成顺推的形式（用 $f'(I,j)$ 更新 $f'(I\cdot C_{w_{p_j}}^k,j+1)$），项全用系数可重集代替，就能在 $O(|S|n^2)$ 的时间内求出所有 $J\in S$ 的 $f(J)$ 了。
你会发现，满足 $J$ 这个集合的 $I\in F$ 有多少个，$f(J)$ 就是多少倍的 $f'(I,0)$，可以归纳证明（不信话把DP式子暴力展开，就会发现它相当于枚举了所有的组合数项）。这样答案就是
$$\sum_{J\in S}f(J)\sum_{< p_0,\cdots,p_{n-1} >\in\mathrm{Perm}(U)}I_J(p_0,\cdots,p_{n-1})$$
这里 $I_J$ 表示任意一个以 $J$ 作为系数可重集的项。最后的问题：$\sum_{< p_0,\cdots,p_{n-1} >\in\mathrm{Perm}(U)}I_J(p_0,\cdots,p_{n-1})$ 怎么求？
可以设计一个类似的DP来求这个东西。记 $g(i,J)=\sum_{p\in\mathrm{Perm}(\{0,1,\cdots,i-1\})}I_J(p)$，枚举 $w_{i-1}$ 的次数 $k$，可得
$$g(i,J)=\sum_{k=0}^{n-1}\mathrm{count}_J(k)C_{w_{i-1}}^kg(i-1,J-[k])$$
其中 $\mathrm{count}_J(k)$ 表示 $J$ 中包含多少个 $k$。同样可以写成顺推的形式，用 $g(i,J)$ 更新 $g(i+1,J+[k])$。另外可以不乘 $\mathrm{count}_J(k)$，而是在最后统计答案的时候乘若干个阶乘。
答案为 $\sum_{J\in S}f(J)g(n,J)$，复杂度 $O(|S|n^2)$，其中 $|S|\le 177970$。实测可以通过 $n=40$ 的数据。程序实现起来并不复杂，但需要考虑清楚转移细节。
由于之前都是假设不考虑 $0$ 的排列而计算的，所以输出时答案需要乘 $(m-n)!$。
另外，对于这道题有一种十分简单的做法（在此orz考场上唯一AC此题的yjqqqaq）：计算 $\frac{m!}{m-n+1}$，该值就是答案。复杂度 $O(m)$，比之前的做法都要快得多。
由于本人暂时不会证明此做法的正确性，故本人尚未写这种做法。
总结
这题现场有20人得到50分以上，也就是说50分做法并不难，但我没有想到，这可以说是我的一个很大问题。
优化DP的方法有很多，但我一直卡在简化状态或者优化转移复杂度上，没有往转移原理方面考虑——如果在放置元素时乘上方案数，无论如何复杂度都要多一个指数级，但是在放置元素时确定它对应的序列区间内的元素方案数，就只要记还允许放几个就够了。DP遇到困难时一定要多变通。
另外100分做法涉及一类特殊状态DP，这种问题我还很不熟悉，以后需要加深这种特殊状态DP的钻研。
T3：温暖会指引我们前行
考场情况
一开始看题，很快就分析出最大字典序路径在最大生成森林上。
然后很快写完25分暴力。随后发现测试点6~14所有的find事件都在move事件之前，意味着最大生成森林的形态不会变，因此预处理LCA以后 $u,v$ 路径长度就是 $\mathrm{dep}_u+\mathrm{dep}_v-2\mathrm{dep}_{\mathrm{LCA}(u,v)}$。修改边权相当于子树深度加一个数，用BIT维护。这样就有70分了。
最后30分树的形态会变，好像要LCT？然而并不是很懂LCT那一套理论于是就不会了……然后就弃疗了。
最后得分：70
考后分析
考后补了一下LCT，然后才会做这题。
首先答案路径在最大生成森林上这个性质是对的，证明不再赘述。
当有加边操作时，最大生成森林会发生怎样的变化呢？考虑图 $G$ 和图 $G+e$（$e$ 为新加入的边）的最大生成森林 $T$ 和 $T'$ 的差别，在 Kruskal 算法的过程中，加入 $t$ 值比 $e$ 大的边时，$T$ 和 $T'$ 相同，加入 $e=(u,v)$ 时，如果 $T$ 中 $u,v$ 连通，那么这条边不被加入，最后 $T'=T$；如果 $u,v$ 分在两个不同的连通块 $A,B$ 中，那么 $e$ 会被加入 $T'$，接下来有两种情况，一种是最后 $T$ 中 $A,B$ 没被连起来，这种情况 $T'=T+e$，另一种是最后 $T$ 中 $A,B$ 被连起来，记 $G$ 中将 $A,B$ 连起来的边是 $e'$，则 $e'$ 不会被加入 $T'$，加入之后接下来的过程就相同了，这时候 $T'=T+e-e'$。
于是加入 $e=(u,v)$，如果 $u,v$ 不连通就直接把 $e$ 加入最大生成森林，否则找出 $u,v$ 路径上 $t$ 最小的边 $e'$，这条边就是在求 $G$ 的最大生成森林时最后连通 $u,v$ 的边，如果 $e'$ 的 $t$ 值比 $e$ 小，在 Kruskal 过程中 $e'$ 在 $e$ 之后处理，不会被加入，因此加入 $e$，删掉 $e'$；如果 $e'$ 的 $t$ 值比 $e$ 大，它在 $e$ 之前处理，则 Kruskal 过程中 $e$ 加入时 $u,v$ 已连通，从而 $e$ 不会被加入，因此不加入 $e$ 即可。
这里需要进行的操作是维护生成森林，支持询问链上最大的边、链上的边权和，以及加边和删边。这些操作可以用 LCT 进行维护，时间复杂度 $O(m\log n)$，可以得到 100 分。
值得一提的是，LCT可以修改点权以及查询链上最大点权以及点权和，如何用于实现修改边权和查询链上边权？对于树上的边 $e=(a,b)$，在LCT中不连 $e$ 这条边，而是对于边 $e$ 建立一个节点 $v_e$，令 $v_e$ 的点权为 $e$ 的边权（原有的点权都是 $0$），然后连边 $(a,v_e)$ 和 $(b,v_e)$。显然这样得到的图仍然是森林，并且对于两点 $u,v$，若原树上删去边 $e$ 会使 $u,v$ 不连通，则新树上删去点 $v_e$ 同样会使 $u,v$ 不连通，反之亦然。因此新树上 $u$ 到 $v$ 的路径点权序列就是原树上 $u$ 到 $v$ 的路径边权序列插入一些无用的 $0$。这样，把边用点来维护，无论查询最大边权还是查询边权和都是查询链上最大点权以及点权和问题，LCT直接维护就行了。
总结
这题在现场是一道20人AC的题，且没AC的人大多是由于写挂导致的，并不是不会做，正如immortalCO所说的这题是一道“模板题”。然而我模板题都不会还能说什么呢，只能说自己水平实在太差了。
看来还是要多练一些模板，比如LCT、FWT之类的。
Day 4
T2：汽水
考场情况
看完题，先写了个 $O(n^2)$ 的第一档暴力20分程序交上去，然后去做下一题了。
离比赛剩不到90min的时候回来搞这题，看到和平均值有关的问题联想到二分答案，二分一个 $M$，判断是否存在一条路径，记经过的边为 $\{e_i\}_{i=0}^{L-1}$，使得 $\lvert\frac{\sum_{i=0}^{L-1}w_{e_i}}{L}-k\rvert < M$，即
$$\begin{cases}(k+M)L-\sum_{i=0}^{L-1}w_{e_i}>0\\ \sum_{i=0}^{L-1}w_{e_i}+(M-k)L>0\end{cases}$$
这就是对于每条边 $e$ 定义两个新权值 $a_e=k+M-w_e$，$b_e=w_e+M-k$，则需要判断是否存在一条路径 $\{e_i\}_{i=0}^{L-1}$ 使得 $\sum_{i=0}^{L-1}a_{e_i} > 0$ 且 $\sum_{i=0}^{L-1}b_{e_i} > 0$。
然后我只想到了树分治……那就来点分治，分治完相当于求有多少对 $u,v$ 满足 $u,v$ 不在同一个子树内，且 $A_u+A_v > 0,B_u+B_v > 0$，其中 $A_u,B_u$ 表示根到 $u$ 的路径上 $a,b$ 权值和，然后好像就能搞出来了可是似乎不太好写……
看了下剩下的时间决定放弃写树分治，还是敲几个部分分保底。发现第二档和第四档部分分，只要二分完以后离散化BIT判一判就行了，这样应该就有60分了吧。
最后得分：40。怎么回事挂了20分？？？
考后分析
后来调之前的代码的时候，才发现我把链的的程序复制到菊的程序里面结果菊的程序里面把 $a_i$ 和 $-a_i$ 都加进离散化数组里了，可是数组只开了 $n$ 于是这20分全没了。
以下是考后写、调这题的过程：
首先码了个点分治，然后二分答案 $M$，预处理出重心 $g$ 到每个点 $v$ 的路径上 $a$ 权值和 $A_v$、$b$ 权值和 $B_v$、所在的子树编号 $c_v$（一个子树就是删掉 $g$ 关联的边之后的一个连通块，$g$ 单独在一个子树）。
现在复杂度已经2个log了，然后是不是接着得线性才能过？开始分析：如果枚举了路径的一个点 $u$，那么要找另一个 $v$ 使得 $A_v > -A_u,B_v > -B_u,c_v\ne c_u$。好像就算没有最后一个条件也得对某一维排序对另一维求最大值= =能不能在预处理的时候排好序？意识到这是错的，思考了一会儿没什么希望好像只能3个log……
3个log的做法很好想，就是用一个数据结构维护一个点集 $S$，然后遍历逐个子树，对子树的每个点 $u$ 查询是否存在 $v\in S$ 使得 $A_v > -A_u,B_v > -B_u$，如果存在就表示二分的这个 $M$ 可行，直接退出；如果不存在，就把这个子树的点加进 $S$ 中。如果扫完所有点还是找不到，说明这样的路径不存在，二分的这个 $M$ 不可行。
至于怎么维护点集 $S$，这只需离散化 $A$ 之后用BIT维护后缀 $B$ 的最大值即可。记 $W=\min\{|w_i-k|\}$，复杂度 $O(n\log^2 n\log W)$。
写完过了样例。这个复杂度很爆炸，本机测了 $n=50000$，$k=1$，所有 $w_i=10^{13}$ 的数据并不能在 $5\texttt{s}$ 内出解。接着加了一些常数优化，如分治到小范围时 $n\log^2 n\log W$ 比 $n^2$ 还大得多，这时候改用 $O(n^2)$ 暴力，等等。
接着对拍随机数据居然拍WA了，这样例该是有多弱……然后把调试语句输出了一堆，手画了好久，看了好久才看出打错了几个下标。
总之这题折腾了好久，最后还是过了。花的时间早已超过了90min，幸好考试的时候没去写树分治否则绝对调不出来。
总结
这题的得分情况是：一半以上的选手得到75分以上，其中接近20个100分。40分的成绩是很糟糕的，平均分都没有上。
考场上我完全可以得到60分的。这题反映出的情况是我的代码能力不足，会做的分没法拿到手，根本原因是平时题目写太少。
更多问题
据说这题有复杂度为 $O(n\log n\log W)$ 的2个log的树分治做法，但我仍然不知道怎样优化成2个log。想找题解发现找不到，所以很想知道2个log怎么做。
immortalCO写了个二分答案之后用Splay启发式合并的做法。据说Splay的启发式合并是均摊 $O(n\log n)$ 的？然而我并不会证明或证否。如果能证明是 $O(n\log n)$ 的话就找到了另一种复杂度 $O(n\log n\log W)$ 的算法。
T3：
待更
鄂公网安备 42010202000505 号