← 返回题目列表

Codeforces · 1148/H

H. 神圣潜水员

中文机器翻译题面 查看原题

给你一个最初为空的数组。您需要执行给定格式的 $$$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)$$$,

$$$\operatorname{mex}(S)$$$(其中 $$$S$$$ 是非负整数的多重集)是未出现在该集合中的最小非负整数。例如,$$$\operatorname{mex}(\{2, 2, 3\}) = 0$$$ 和 $$$\operatorname{mex} (\{0, 1, 4, 1, 6\}) = 2$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组的长度。

接下来的 $$$n$$$ 行包含查询的描述。

每 $$$n$$$ 行包含四个非负整数 $$$a'$$$, $$$l'$$$, $$$r'$$$, $$$k'$$$ ($$$0, \leq a', l', r', k' \leq 10^9$$$),描述一个操作。

输出

对于每个查询,打印一个整数 - 该查询的答案。

示例

输入 #1

5
0 0 0 1
0 1 0 5
5 2 1 0
5 2 1 0
2 4 3 3

输出 #1

1
1
2
6
3

输入 #2

5
2 0 0 2
2 0 1 1
0 0 2 0
3 2 2 0
0 2 3 0

输出 #2

0
0
3
0
0

注意

对于第一个示例,$$$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$$$