题意简化

维护 $n$ 个集合 $B_1, B_2, \dots, B_n$，定义：

$$B_i = \left(\bigcap_{j \in A_i} B_j\right) \cup C_i $$

其中：

• $A_i$ 中的元素都 $< i$
• 所有 $C_i$ 两两不相交

已知 $A_i$ 和 $|C_i| = k_i$，支持：

1. 添加新集合 $B_{n+1}$，给定 $A_{n+1}$ 和 $|C_{n+1}|$
2. 修改 $|C_i|$
3. 查询 $\left|\bigcup_{i \in S} B_i\right|$

$n \le 2\times 10^5$，强制在线。

核心思想：树形结构 + LCT

1. 转化为树结构

关键观察：$B_i$ 的定义中，依赖 $A_i$ 中所有 $B_j$ 的交集。

设 $p_i = \text{LCA}$ 意义上的父亲节点：

• $B_i$ 包含 $C_i$（大小 $k_i$）
• 同时包含父节点集合的部分

实际上，可以构建一棵树：

• 节点 $i$ 对应 $B_i$
• 父节点是 $A_i$ 中所有 $j$ 在树上的最近公共祖先（LCA）

2. 查询公式推导

对于查询 $S$，要求 $\left|\bigcup_{i \in S} B_i\right|$。

由于 $C_i$ 两两不相交，答案等于：

$$\sum_{i \in S} |C_i| - \sum_{i<j} |B_i \cap B_j| + \dots $$

但更简单：在树结构中，$B_i$ 包含从根到 $i$ 路径上所有节点的 $C$ 集合。

因此：

$$\left|\bigcup_{i \in S} B_i\right| = \left|\bigcup_{i \in S} (\text{根到 } i \text{ 路径上所有 } C)\right| $$

即：所有查询节点到根路径的并集的大小。

3. 算法实现

使用**LCT（Link-Cut Tree）**维护：

节点信息：

• val[i]：$|C_i|$ 的大小
• sum[i]：子树（Splay树中）的 val 和

操作：

1. Add：

   • 找到 $A_i$ 中所有节点在LCT中的LCA last
   • 创建新节点 nod++
   • 设置父亲 fa[nod] = last
   • val[nod] = k（$|C|$ 大小）
   • access(nod) 更新信息

2. Update：

   • 修改 val[x]
   • 更新节点信息

3. Query：

   • 对查询集合 $S$ 中的每个节点 x：
     • access(x)：将根到 x 的路径变为偏爱路径
     • 如果节点未被访问过（vis[x] != tim）：
       • 累加 sum[x] 到答案
       • 标记已访问
   • 答案为路径并集的大小

关键技巧

1. LCA计算

代码中 LCA(u,v) 通过两次 access 实现：

access(u);
return access(v);

第二次 access 返回的节点就是 LCA。

2. 路径去重

使用 vis[] 数组和 tim 时间戳标记已访问的节点，避免重复计算。

3. 强制在线处理

• 读入的 $A_i$ 中元素需要异或上次答案 lastans
• 注意节点编号从 1 开始（++x）

复杂度分析

• Add：$O(|A_i| \log n)$ 找 LCA
• Update：$O(\log n)$ Splay 操作
• Query：$O(|S| \log n)$
• 总复杂度：$O((n+q)\log n)$，可过 $2\times 10^5$

样例解释

初始：节点1为根（虚拟节点）

操作1：Add 0 1

• $A_1 = \emptyset$，LCA 为 1
• 创建节点2，父节点为1，$|C_2|=1$

操作2：Query 1 1

• 查询节点2：路径 {1,2}，大小 1
• 输出：1

操作3：Update 1 4

• 修改节点2的 $|C|=4$

操作4：Query 1 1

• 查询节点2：路径 {1,2}，大小 4
• 输出：4

代码特点

• 标准 LCT 实现
• vis[] 时间戳去重
• sum[] 维护子树和
• 强制在线异或处理