题解：P12014 [Ynoi April Fool's Round 2025] 牢帽

· · 题解

P12014 [Ynoi April Fool's Round 2025] 牢帽

Problem

星野加奈给你一个 n 个点的无向图，图初始没有边。他还有整数 u,v 和 a_1,a_2,\cdots ,a_n。现在有 q 次操作，操作有四种：

  1. 1 x y ：连接 x,y 之间的边，保证边原先不存在。
  2. 2 x y ：删除 x,y 之间的边，保证边原先存在。
  3. 3 x y ：将 a_x 修改为 y 。
  4. 4 x ：设图分为 C_1,C_2,\cdots ,C_k 共 k 个连通块，求出 \sum_{i=1}^k \prod_{j\in C_i}(a_j+x) \bmod u^v。
时间 3s，空间 512MB。 ### Solution 一种可能不太一样的口胡做法。欢迎大家指错。 对于动态加删边、维护连通块信息，可以使用线段树分治进行维护。 发现 $u\le 10$，也就是说小于 $u$ 的质数只有 $2, 3, 5, 7$。并且次数也很小。 对每个连通块，记录其在模 $2, 3, 5, 7$ 意义下的每个余数的数量。查询 $+x$ 时，只需要知道余数为 $-x$ 的个数。但是这样没有办法知道 $2, 3, 5, 7$ 的个数究竟有多少个（eg：$7+1=2^3$）考虑在个数比较少的时候直接记录数的集合。然后由于 $u, v$ 在开头就给定了，所以不用把每个数的数量都维护满，最大的时候是 $u=10, v=4$，此时需要维护 $4\times 2 + 5\times 5=33$ 个数。然后最劣的情况就是 $u$ 是一个质数，所以维护的数的量级是 $O(uv)$ 的。 时间复杂度：$O(quv \log q \log n)$。