窗口校准
题目描述
给定长度为 n 的序列 a1,a2,…,an。所有数值运算都在模 P=998244353 的意义下进行。需要依次处理 m 次操作。
操作一:1 l r k(窗口校准)
其中 1≤k≤r−l。定义长度为 k 的窗口和
Wi=j=i∑i+k−1aj,l≤i≤r−k+1.
保持 al,al+1,…,al+k 的当前值不变,修改 al+k+1,…,ar,使修改后的窗口和按起点递增的顺序构成等差数列,即存在一个模 P 的数 c,满足
Wi+1−Wi=c,l≤i≤r−k.
这里的 Wi 均由修改后的序列计算,公差 c 可以随操作变化。区间 [l,r] 之外的元素不变。可以证明满足要求的结果存在且唯一。当 k=r−l 时,此操作不改变序列。
操作二:2 l r u v(区间仿射)
对于每个 i∈[l,r],令 ai←uai+v。
操作三:3 l r(区间求和)
输出 ∑i=lrai 对 P 取模的结果。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
第三行包含整数 m。
接下来 m 行,每行描述一次操作,格式如题目描述。
输出格式
对于每个操作三,输出一行一个整数,表示查询结果,取值范围为 [0,P−1]。
样例 1
输入
8
1 4 6 9 13 18 24 31
8
3 1 8
1 1 8 3
3 1 8
3 4 7
2 3 6 2 1
3 1 8
1 2 7 2
3 5 8
输出
106
83
52
128
125
样例 1 解释
第一次校准后,序列为 1,4,6,9,12,14,17,20,窗口和为 11,19,27,35,43,51,公差为 8。
执行区间仿射后,序列为 1,4,13,19,25,29,17,20。最后一次校准保留位置 2 至 4,得到 1,4,13,19,28,34,43,20,最后四项之和为 125。
样例 2
输入
5
4 7 2 9 1
10
3 1 1
2 3 3 0 10
3 2 4
1 1 3 2
3 1 5
1 1 5 1
3 3 5
2 1 1 2 3
2 5 5 0 0
3 1 5
输出
4
26
31
39
41
样例 2 解释
第一次仿射操作令 a3=10。1 1 3 2 不改变序列;1 1 5 1 将序列变为 4,7,10,13,16。最后两次仿射操作后,序列为 11,7,10,13,0。
样例 3
输入
6
998244351 1 998244351 4 0 3
12
3 1 6
1 1 5 2
3 1 6
2 2 5 998244352 998244352
3 1 6
2 1 6 0 0
1 2 6 1
3 2 5
2 6 6 998244352 998244352
3 5 6
1 4 6 1
3 1 6
输出
4
998244352
998244352
0
998244352
0
样例 3 解释
模 P 意义下,998244351 与 998244352 分别表示 −2 与 −1。第一次校准后,序列为 −2,1,−2,1,−2,3;随后的仿射操作得到 −2,−2,1,−2,1,3。将整个序列变为零后,校准仍得到全零序列。倒数第二次修改将 a6 变为 −1,最后一次校准又将其变为 0。
数据范围与子任务
对于所有数据:
- 1≤n,m≤105;
- 0≤ai,u,v<P;
- 1≤l≤r≤n;
- 操作一满足 1≤k≤r−l;
- 至少有一次操作三。
记 N=max(n,m)。
| 子任务 |
分值 |
附加限制 |
| 1 |
20 |
N≤1000 |
| 2 |
15 |
没有操作一 |
| 3 |
包含操作一,且所有操作一均满足 k=1 |
| 4 |
20 |
N≤10000 |
| 5 |
30 |
无 |
各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。更多样例见附加文件 samples.zip。