题解：CF2129E Induced Subgraph Queries

沉石鱼惊旋 · 2025-08-08 14:58:14 · 题解

看上去就一眼莫队，你可以轻松地在 \mathcal O(\deg_u) 的复杂度内移动指针。

先说这个轻松怎么做到。不拿发现 [1,n] 里选若干个数异或起来，你考虑每个二进制位都放 1。其实就是 \mathcal O(n) 量级的，不超过 2n-1。

然后使用值域分块，就是 [1,V] 分 \sqrt V 段，然后维护每一段有多少数，显然直接修改就是 \mathcal O(1)，查询先暴力跳大段然后锁定到一个段里去枚举答案。这样修改 \mathcal O(1) 查询 \mathcal O(\sqrt V)。

现在的问题是，如果一个度数很大的点反复横跳，就爆炸了。

我们考虑这样子修改莫队算法的分块部分：设 p_i=\sum\limits_{j=1}^i \deg_i+1，然后按 \sqrt{p_n} 为块长分块，每一个 i 就在第 \frac{p_i}{\sqrt{p_n}} 这一块。