← 返回题目列表

AtCoder · stpc2025_1_m

M. 多种方法

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

配点 : 100 点

問題文

N 有一个由若干广场左右排列的公园,广场从左到右顺序为 0,1,\dots, N-1 编号已附上。

公园中,0, 1, \dots, N-1 它是一个具有 N 有很多人。你 0 以上 N-1 声明以下的非负整数序列时, X=(X_1,X_2,\dots, X_{|X|}) 这些人有如下的 行進 。 对于

  1. 各 i = 0,1,\dots, N-1 关于人 求 i 是正方形 i 。
  2. 各 j = 1, 2, \dots, |X| ,按此顺序执行以下操作: 方格内除
    • 広場 X_j 以外的所有人都可以从自己的方格移动到本方格。 X_j 走向广场 移动 1 。 在线回答

0 以上 N-1 由小于或等于的非负整数组成的长度 在 M 栏 A=(A_0,A_1,\dots, A_{M-1}) 。 对于

Q 疑问。 给出 i=1,2,\dots, Q , 当我输入 i 个查询是一个整数 查找 t_i',L_i',R_i',P_i' 。首先,请按照以下步骤操作 请恢复 t_i,L_i,R_i,P_i 。

  • \mathrm{ans}_0=0 、\mathrm{ans}_i= ( i 答案)。
  • 本例如下 恢复 t_i,L_i,R_i,P_i 。
    • t_i=((t_i' + \mathrm{ans}_{i-1})\bmod 2)
    • a=((L_i' + \mathrm{ans}_{i-1})\bmod M)
    • b=((R_i' + \mathrm{ans}_{i-1})\bmod M)
    • L_i=\min(a,b)
    • R_i=\max(a,b)
    • P_i=((P_i' + \mathrm{ans}_{i-1})\bmod N)

其中非负整数 表示除以 a 和一个正整数 从范围 b 反对 (a\bmod b) 是 您也可以写 a 该值应乘以 b 所得的余数。这个值是 小于 0 以上 b 。

这样获取 请回答以下 t_i,L_i,R_i,P_i 的查询。 当人们游行并宣布

  • t_i=0 : X = (A_{L_i},A_{L_i+1}\dots, A_{R_i}) 请回答 P_i 所在方格的编号。
  • t_i=1 : X = (A_{L_i},A_{L_i+1}\dots, A_{R_i}) 行军并宣布时 请告诉我们 P_i 中有多少人。 第

制約

  • 所有输入均为整数
  • 1\le N,M,Q\le 2\times 10^5
  • 0\le A_i\le N-1\ (0\le i\le M-1)
  • 0\le t_i',t_i\le 1\ (1\le i\le Q)
  • 0\le L_i',R_i'\le M-1\ (1\le i\le Q)
  • 0\le L_i\le R_i\le M-1\ (1\le i\le Q)
  • 0\le P_i',P_i\le N-1\ (1\le i\le Q)

入力

输入按以下格式给出。

N M Q
A_0 A_1 \dots A_{M-1}
t_1' L_1' R_1' P_1'
t_2' L_2' R_2' P_2'
\vdots
t_Q' L_Q' R_Q' P_Q'

出力

Q 行。i=1,2,\dots, Q 关于 i 在线 i 个查询的答案 当我们游行并宣布 \mathrm{ans}_i 。


入力例 1

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

出力例 1

2
0
3

1 个查询中 给出了 (t_i,L_i,R_i,P_i)=(0,1,3,2) 。 X = (A_1,A_2,A_3)=(2,3,2) 时,人们 2 是正方形 导航至 2\to 2\to 3\to 2 。因此答案是 当你宣布 2 。

2 个查询中 给出了 (t_i,L_i,R_i,P_i)=(1,2,4,3) 。 X = (A_2,A_3,A_4)=(3,2,1) 并游行时,每个方格的人数将为 0 开始 0,4,0,0 。因此答案是 0 。

3 个查询中 给出了 (t_i,L_i,R_i,P_i)=(1,4,4,1) 。 X = (A_4)=(1) 并游行时,每个方格的人数将为 0 开始 0,3,1,0 。因此答案是 3 。


入力例 2

7 4 1
3 3 3 3
1 3 0 3

出力例 2

7