抽奖插件¶
- 参考时间限制：8.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB
背景故事¶
村长正在调试抽奖插件。参与者可以退出，也可以修改幸运数字并重新加入。插件需要在指定时刻找出幸运数字最接近目标值的人，并严格执行同分时的编号规则。
形式化问题描述¶
共有 \(n\) 人，编号为 \(1\) 到 \(n\) .初始所有人都在场，编号 \(i\) 的幸运数字为 \(i\) .依次处理 \(m\) 个事件。
令 \(a_0=A\) ，对每个事件 \(i\) 计算一次
\[
a_i=(a_{i-1}B+C)\bmod n+1,\qquad t_i=a_i
\]
事件分为三种：
- 查询：在场者中选幸运数字与 \(t_i\) 的绝对差最小的人。差相同时选幸运数字更小的；幸运数字仍相同时，若该数字大于 \(t_i\) ，选编号最小者，否则选编号最大者。无人时答案为 \(0\) .查询不改变状态。
- 修改：给定编号 \(d_i\) ，把该人的幸运数字改为 \(t_i\) ；如果已经退出，则同时重新加入。
- 退出：让编号为 \(t_i\) 的人退出；已经退出时没有变化。
输入给出 \(q\) 个查询事件的位置，以及 \(k\) 个修改事件的位置和对象。其他事件均为退出事件。每个事件都推进一次上述序列，包括查询和无效退出。
输入格式¶
第一行三个整数 \(A,B,C\) .第二行四个整数 \(n,m,q,k\) .第三行 \(q\) 个严格递增的事件编号，表示查询位置。第四行 \(k\) 对整数 \(p_i,d_i\) ，表示第 \(p_i\) 个事件修改参与者 \(d_i\) ；其中 \(p_i\) 严格递增。两类事件编号互不重叠。\(q=0\) 或 \(k=0\) 时对应行为空。
输出格式¶
按事件顺序输出 \(q\) 行，每行一个查询结果。\(q=0\) 时不输出任何整数。
样例 1¶
输入¶
5 3 3
5 8 4 2
3 6 7 8
2 3 5 3
输出¶
2
1
2
3
样例 2¶
输入¶
1 13 17
11 30 10 8
5 13 17 18 19 20 23 25 27 30
1 1 8 1 9 1 15 10 21 10 26 4 28 4 29 10
输出¶
7
4
4
6
8
4
4
7
6
4
样例 3¶
输入¶
1 1 17
11 60 15 8
5 13 17 18 19 20 23 25 27 30 40 45 55 58 60
1 1 8 1 9 1 15 10 21 10 26 4 28 4 29 10
输出¶
3
3
9
10
2
9
9
9
2
2
2
0
0
0
0
样例解释¶
样例 1 的目标值依次为 \(4,1,2,5,4,1,2,5\) ，四次查询结果为 \(2,1,2,3\) .样例 3 后四次查询时所有人都已退出，因此输出 \(0\) .
数据范围与保证¶
所有数据满足 \(1\le n\le3500000\) ，\(0\le m\le4000000\) ，\(0\le q,k\le200000\) ，\(q+k\le m\) ，\(0\le A,B,C\le10^9\) .所有事件编号在 \([1,m]\) 内，修改对象编号在 \([1,n]\) 内。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |