链表 (chain) 问题：连通块计数与权值修改

链表 (chain) 问题：连通块计数与权值修改

题目描述

有一个长度为 $n$ 的链表，第 $i$ 个节点与第 $i+1$ 个节点相连，每个节点有一个权值 $a_i$。

有 $m$ 次操作，每次操作有如下两种可能：

• `Q x` 表示询问仅保留权值 $\ge (x \operatorname{xor} Last)$ 的节点时的连通块个数。
• `C k y` 表示将第 $(k\operatorname{xor} Last)$ 个节点的权值变为 $(y \operatorname{xor} Last)$。

其中 $\operatorname{xor} Last$ 表示异或上一次询问操作 `Q x` 的答案，$Last$ 初始时为 0。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_{1\dots n}$。

接下来 $m$ 行，每行一个操作 `Q x` 或 `C k y`。

输出格式

对于每个询问操作 `Q x`，一行一个整数，表示答案。

样例 #1

样例输入 #1

5 7
3 2 1 3 5
Q 1
Q 2
Q 3
C 2 2
C 5 3
C 4 2
Q 2

样例输出 #1

1
2
1
3

样例 #2

样例输入 #2

见附件 chain2.in

样例输出 #2

见附件 chain2.ans

提示

【样例说明 1】

询问操作的 $(x \operatorname{xor} Last)$ 分别为 $1,3,1,3$，最后一次询问前的链表节点权值分别为 $3,2,3,2,3$。

【数据范围】

• 对于前 $30%$ 的数据，$n,m \le 5000$。
• 对于另 $30%$ 的数据，没有 `C k y` 操作。
• 对于另 $20%$ 的数据，$n,m \le 10^5$。
• 对于 $100%$ 的数据，$1 \le n,m \le 5 \times 10^5$，$1 \le (k\operatorname{xor} Last) \le n$，$1 \le (x\operatorname{xor} Last),(y\operatorname{xor} Last) \le 5 \times 10^5$。

思路

首先，我们可以使用一个链表来存储节点的权值，并使用一个数组来记录每个节点的前驱和后继的索引。

对于询问操作 `Q x`，我们需要遍历链表，统计节点权值大于等于 $(x \operatorname{xor} Last)$ 的连通块个数。具体操作如下：

1. 初始化一个变量 `count` 为 0，用于记录连通块个数。
2. 从链表的头节点开始，依次遍历链表。
3. 如果当前节点的权值大于等于 $(x \operatorname{xor} Last)$，则将 `count` 加 1。
4. 如果当前节点的后继索引不为 -1 且后继节点的权值小于 $(x \operatorname{xor} Last)$，则将 `count` 加 1。
5. 更新 `Last` 为当前询问操作的答案，即 `count`。
6. 输出 `count`。

对于修改操作 `C k y`，我们需要修改第 $(k\operatorname{xor} Last)$ 个节点的权值为 $(y \operatorname{xor} Last)$。具体操作如下：

1. 计算节点的索引 `index` 为 $(k\operatorname{xor} Last)$。
2. 更新节点的权值为 $(y \operatorname{xor} Last)$。

算法实现步骤

1. 定义一个链表 `list`，用于存储节点的权值。
2. 定义一个数组 `prev`，用于记录每个节点的前驱索引。
3. 定义一个数组 `next`，用于记录每个节点的后继索引。
4. 定义一个变量 `Last`，初始化为 0，用于记录上一次询问操作的答案。
5. 读取输入，初始化链表 `list` 和数组 `prev` 和 `next`。
6. 依次处理每个操作：
   • 如果是询问操作 `Q x`，则进行查询操作：
     • 初始化一个变量 `count` 为 0。
     • 从链表的头节点开始，依次遍历链表。
     • 如果当前节点的权值大于等于 $(x \operatorname{xor} Last)$，则将 `count` 加 1。
     • 如果当前节点的后继索引不为 -1 且后继节点的权值小于 $(x \operatorname{xor} Last)$，则将 `count` 加 1。
     • 更新 `Last` 为 `count`。
     • 输出 `count`。
   • 如果是修改操作 `C k y`，则进行修改操作：
     • 计算节点的索引 `index` 为 $(k\operatorname{xor} Last)$。
     • 更新节点 `list[index]` 的权值为 $(y \operatorname{xor} Last)$。

代码实现

# 这里请根据你的代码实现进行填充