题解：P13012 【MX-X13-T7】「KDOI-12」No one can be anything without comparison.

· · 题解

这个 12s, 2GB 看起来就让人很有做的欲望。NOI 前几天谁还做正经题啊。

不需要树分块，好像比正解简单一点？而且只需要保留一棵树的形态，剩下的的限制只要是区间包含单点就可以做。但是复杂度和正解相同，可能本质相同吧。（upd：确实本质相同，我的做法是将祖先关系描述成一个点子树的一段区间，另一个做法是将祖先关系描述成一个点到根的链，都是转化成了某种线性的结构）

本来以为是巨大数据结构的，写完发现超级好写，失策了。

思路

先转化一下祖先的关系。放在 dfs 序上，设在第 i 棵树上每个点的新编号是 id_{i,j}，每个点包含的编号区间是 [l_{i,j},r_{i,j}]（有 id_{i,j}+1=l_{i,j}）。那么一个有序对 a_1,a_2,\cdots,a_k 合法等价于 \forall 1 \le i \le k,id_{i,a_{i \bmod k+1}} \in [l_{i,a_i},r_{i,a_i}]。

首先考虑 \mathcal O(n^2) 左右的复杂度怎么做。这是一个环的限制，所以无论如何是需要枚举一个点的。枚举 a_1。设 dp_{i,j} 表示走到第 i 棵树的第 j 个点的方案数。对于一个状态可以转移到一个区间，所以差分并还原即可。注意，转移后的下标是新编号，需要转化为原编号。

统计答案时，最后的限制是 a_k 在第 k 棵树上是 a_1 的祖先。所以考虑解决这个限制。这里有两种思路，一种是从上到下 dfs，在 a_k 处修改，a_1 处查询，再撤销 a_k 的贡献。另一种是 dsu on tree，a_1 处修改，a_k 处查询。先保留这两种思路，之后再看哪种更合适。

考虑 k=3 怎么做。对于第一种思路，在 a_1 处查询时 a_2 是一段区间，贡献是 a_2 对应的区间包含了多少个修改的 a_3。考虑分块，那么散块就是单点修改区间查询（可以使用 \mathcal O(\sqrt{n}) - \mathcal O(1) 的分块平衡）。整块有很多区间，但值域只有 n，所以可以压缩信息。具体地，预处理，使用之前提到的做法求出每一个块对于每个 a_3 的答案。对于每个 a_3 的修改更新每个块的答案即可。对于第二种思路，思路其实是一样的。将 a_1 的贡献分为整块和散块两部分，对于整块打上加一的 tag，散块区间加。查询 a_3 时遍历每个块就可以算出整块的贡献，对于散块的贡献单点查询即可。

可以发现这两种思路本质是一样的。都是将贡献拆成整块和散块两部分，对于 a_1 和 a_3 在某一个整块上都有特定的贡献（a_1 是 1，a_3 是预处理的值），答案是将两者相乘。而散块就是将单点和区间的修改和查询的对应关系交换了，它们都是好做的。而第二种思路多一个 \log，所以接下来只考虑第一种思路。

可以发现整块的贡献可以扩展到 k>3，因为值域是 n，所以随时都在压缩信息，信息量不会随着树的个数而指数增加。而散块终究是不好做的。于是考虑将块长开很小，对于散块暴力枚举并递归到下一棵树的子问题。最开始我以为这样做的复杂度是 \mathcal O(B^3) 的，于是可以设 B=n^{\frac{1}{4}}，就做完了。写完才发现递归到下一棵树的时候还需要枚举整块，在最后一棵树的时候会出现 B^2\cdot \dfrac{n}{B}，非常不牛。

能改进吗？考虑将第二棵树的块长开大一点，第三棵树的块长再开大一点，这样没准能平衡。设 B_1,B_2,B_3 分别为三棵树的块长，那么运算次数是 \dfrac{n}{B_1}+B_1\dfrac{n}{B_2}+B_1B_2\dfrac{n}{B_3}+B_1B_2B_3。取 \log，从后到前依次取等，可以得到 B_1=n^{\frac{1}{8}},B_2=n^{\frac{1}{4}},B_3=n^{\frac{1}{2}}。这样就得到了 \mathcal O(n^{\frac{15}{8}}) 的优秀复杂度（而且还没算预处理的 k^2）。

我还真写了这个思路，甚至只跑了 40 多秒。其实确实合理，\mathcal O(n^2) 估计就这么快，这个思路主要是为了压缩空间。

当我准备卡常的时候我突然看到了一段区间求和的代码。在递归的过程中完全不需要遍历整块！只需要在修改的时候动态维护前缀和即可。那为什么最初没发现呢？因为 k=3 的时候块的个数与块长都是 \sqrt{n}，就没有区分它们，但是现在块的个数对复杂度产生影响了。所以要跳出思维定式。但是一步一步推过来想发现这一点对于我来说可能还挺难的。

于是这样的复杂度就是 \mathcal O(\dfrac{n^2}{B}k^2+nB^3) 了。取 B=n^{\frac{1}{4}}k^{\frac{1}{2}} 可以得到 \mathcal O(n^{\frac{7}{4}}k^{\frac{3}{2}}) 的复杂度。我取的是 1000,80,30，最后卡着时限过的。想要更快可能可以将整块的询问离线，这样可以优化空间访问。

提交记录