CF1148H Holy Diver

你有一个初始为空的数组。你需要进行 $n$ 次如下格式的操作： - “$a$ $l$ $r$ $k$”：将 $a$ 添加到数组末尾。之后，统计有多少整数对 $x, y$ 满足 $l \leq x \leq y \leq r$ 且 $\operatorname{mex}(a_{x}, a_{x+1}, \ldots, a_{y}) = k$。 数组中的元素按照加入顺序从 $1$ 开始编号。 为了增加难度，题目不会直接给出操作的真实参数，而是给出 $a'$、$l'$、$r'$、$k'$。在第 $i$ 次操作中，你需要按如下方式计算 $a$、$l$、$r$、$k$： - $a := (a' + lans) \bmod(n + 1)$， - $l := (l' + lans) \bmod{i} + 1$， - $r := (r' + lans) \bmod{i} + 1$， - 如果 $l > r$，交换 $l$ 和 $r$， - $k := (k' + lans) \bmod(n + 1)$， 其中 $lans$ 是上一次操作的答案，初始时 $lans = 0$。$i$ 是当前操作编号，操作从 $1$ 开始编号。$\operatorname{mex}(S)$ 表示集合 $S$（多重集）中未出现的最小非负整数。例如，$\operatorname{mex}(\{2, 2, 3\}) = 0$，$\operatorname{mex}(\{0, 1, 4, 1, 6\}) = 2$。

第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示数组的长度。 接下来的 $n$ 行，每行包含四个非负整数 $a'$、$l'$、$r'$、$k'$（$0 \leq a', l', r', k' \leq 10^9$），描述一次操作。

对于每次操作，输出一个整数，表示该操作的答案。

对于第一个样例，解码后的 $a$、$l$、$r$、$k$ 如下： $a_1=0, l_1=1, r_1=1, k_1=1$ $a_2=1, l_2=1, r_2=2, k_2=0$ $a_3=0, l_3=1, r_3=3, k_3=1$ $a_4=1, l_4=1, r_4=4, k_4=2$ $a_5=2, l_5=1, r_5=5, k_5=3$ 对于第二个样例，解码后的 $a$、$l$、$r$、$k$ 如下： $a_1=2, l_1=1, r_1=1, k_1=2$ $a_2=2, l_2=1, r_2=2, k_2=1$ $a_3=0, l_3=1, r_3=3, k_3=0$ $a_4=0, l_4=2, r_4=2, k_4=3$ $a_5=0, l_5=3, r_5=4, k_5=0$ 由 ChatGPT 4.1 翻译