#P17936. Many Approaches
Many Approaches
Many Approaches
有 个广场从左到右编号为 ,以及同样编号的 个人。
给定一个元素均在 内的整数序列 ,一次行进定义如下:
- 先让每个人 回到广场 。
- 按顺序处理 中的每个元素 :所有不在广场 的人同时向 的方向移动一个广场;已经在 的人不动。
给定长度为 的序列 。你需要在线回答 个询问。每个询问输入四个加密整数 。
令 , 为上一个询问的答案。先解码:
$$a=(L'_i+\mathrm{ans}_{i-1})\bmod M,\quad b=(R'_i+\mathrm{ans}_{i-1})\bmod M,$$$$L_i=\min(a,b),\quad R_i=\max(a,b),\quad P_i=(P'_i+\mathrm{ans}_{i-1})\bmod N.$$然后以 进行一次独立的行进:
- 若 ,回答人 最终所在的广场编号;
- 若 ,回答最终位于广场 的人数。
每次询问都从人 位于广场 的初始状态开始,前一次行进不会改变下一次行进的初始状态。
输入格式
N M Q
A_0 A_1 ... A_{M-1}
t'_1 L'_1 R'_1 P'_1
...
t'_Q L'_Q R'_Q P'_Q
输出格式
输出 行,按顺序回答询问。
数据范围
,。
,,。所有输入均为整数。
样例 1
输入:
4 5 3
0 2 3 2 1
0 1 3 2
1 0 2 1
1 4 4 1
输出:
2
0
3
样例 2
输入:
7 4 1
3 3 3 3
1 3 0 3
输出:
7