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

星野加奈给你一个

n

个点的无向图，图初始没有边。他还有整数

u,v

和

a_1,a_2,\cdots ,a_n

。现在有

q

次操作，操作有四种：

1 x y ：连接 $x,y$ 之间的边，保证边原先不存在。
2 x y ：删除 $x,y$ 之间的边，保证边原先存在。
3 x y ：将 $a_x$ 修改为 $y$ 。
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$ 。

1\leq n,q\leq 10^5,1\leq u\leq 10,1\leq v\leq 4,0\leq a_i <10^4

，

3

操作中

y

、

4

操作中

x

均为小于

10^4

的非负整数。

时间 3s，空间 512MB。

一种可能不太一样的口胡做法。欢迎大家指错。

对于动态加删边、维护连通块信息，可以使用线段树分治进行维护。

发现

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)

。

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