AT_stpc2025_1_m Many Approaches

有一个公园，里面有 $N$ 个广场排成一排，每个广场从左到右依次编号为 $0,1,\dots, N-1$。 公园里有 $N$ 个人，每个人的编号为 $0,1,\dots, N-1$。当你声明一个由 $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$ 的方向移动一个广场的距离。 给定一个长度为 $M$，每个元素都是 $0$ 到 $N-1$ 之间的非负整数的序列 $A=(A_0,A_1,\dots, A_{M-1})$。 请在线回答 $Q$ 个查询。对于第 $i$ 个查询（$i=1,2,\dots, Q$），给出整数 $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-1$。 对于恢复得到的 $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$ 的广场上的人数。

输入格式如下： > $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$ 行输出第 $i$ 条查询的答案 $\mathrm{ans}_i$。

### 样例解释 1 对于第 $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$ 号到 $3$ 号依次为 $0,4,0,0$。因此答案为 $0$。 对于第 $3$ 条查询，有 $(t_i,L_i,R_i,P_i)=(1,4,4,1)$。声明 $X=(A_4)=(1)$ 并按照行进规则执行，最终每个广场上的人数从 $0$ 号到 $3$ 号依次为 $0,3,1,0$。因此答案为 $3$。 ### 数据范围 - 所有输入均为整数 - $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)$ 由 ChatGPT 5 翻译