#P6900. 看节目
看节目
题目描述
最初,第 个节目在时刻 举行,观看它可获得愉悦值 。
主办方使用同一个排列 调整节目顺序。每次重排都将重排之前位于时刻 的节目移到时刻 ,所有节目同时移动。给定参数 ,如下生成排列。
seed = x
for i = 1 to n:
p[i] = i
seed = (seed * y) mod 998244353
j = seed mod i + 1
swap(p[j], p[i])
需要处理多次重排操作和区间询问。每次区间询问求当前时刻 到 (含端点)举行的节目愉悦值之和,对 取模。
输入格式
第一行四个整数 ,分别表示节目数、操作数及生成排列的两个参数。
第二行 个整数 ,依次表示各节目的愉悦值。
接下来 行,每行是一种操作。
1 k:将当前节目顺序连续重排 次。2 l r:查询当前时间区间 的愉悦值之和。
输出格式
每个类型 的操作输出一行一个整数,表示查询结果对 取模后的值。
样例
5 5 23333 66666
1 2 1 3 8
1 1
2 2 4
2 1 3
1 2
2 2 5
5
12
14
生成的排列为 。第一次重排后,按时刻排列的愉悦值变为 。之后两次重排先得到 ,再得到 。
数据范围
对于全部数据,,,,操作类型为 或 ,,。
| 原题数据比例 | 附加限制 |
|---|---|
| 20% | , |
| 40% | |
| 另外 10% | 所有询问满足 |
原题时间限制 6 秒,内存限制 512 MB。
By Mr_Spade