#P18909. [2026多校联测]窗口校准

[2026多校联测]窗口校准

窗口校准

题目描述

给定长度为 nn 的序列 a1,a2,…,ana_1,a_2,\ldots,a_n。所有数值运算都在模 P=998244353P=998244353 的意义下进行。需要依次处理 mm 次操作。

操作一:1 l r k(窗口校准)

其中 1≤k≤r−l1\le k\le r-l。定义长度为 kk 的窗口和

Wi=∑j=ii+k−1aj,l≤i≤r−k+1.W_i=\sum_{j=i}^{i+k-1}a_j,\qquad l\le i\le r-k+1.

保持 al,al+1,…,al+ka_l,a_{l+1},\ldots,a_{l+k} 的当前值不变,修改 al+k+1,…,ara_{l+k+1},\ldots,a_r,使修改后的窗口和按起点递增的顺序构成等差数列,即存在一个模 PP 的数 cc,满足

Wi+1−Wi=c,l≤i≤r−k.W_{i+1}-W_i=c,\qquad l\le i\le r-k.

这里的 WiW_i 均由修改后的序列计算,公差 cc 可以随操作变化。区间 [l,r][l,r] 之外的元素不变。可以证明满足要求的结果存在且唯一。当 k=r−lk=r-l 时,此操作不改变序列。

操作二:2 l r u v(区间仿射)

对于每个 i∈[l,r]i\in[l,r],令 ai←uai+va_i\leftarrow ua_i+v。

操作三:3 l r(区间求和)

输出 ∑i=lrai\sum_{i=l}^r a_i 对 PP 取模的结果。

输入格式

第一行包含整数 nn。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

第三行包含整数 mm。

接下来 mm 行,每行描述一次操作,格式如题目描述。

输出格式

对于每个操作三,输出一行一个整数,表示查询结果,取值范围为 [0,P−1][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,201,4,6,9,12,14,17,20,窗口和为 11,19,27,35,43,5111,19,27,35,43,51,公差为 88。

执行区间仿射后,序列为 1,4,13,19,25,29,17,201,4,13,19,25,29,17,20。最后一次校准保留位置 22 至 44,得到 1,4,13,19,28,34,43,201,4,13,19,28,34,43,20,最后四项之和为 125125。

样例 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=10a_3=10。1 1 3 2 不改变序列;1 1 5 1 将序列变为 4,7,10,13,164,7,10,13,16。最后两次仿射操作后,序列为 11,7,10,13,011,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 解释

模 PP 意义下,998244351998244351 与 998244352998244352 分别表示 −2-2 与 −1-1。第一次校准后,序列为 −2,1,−2,1,−2,3-2,1,-2,1,-2,3;随后的仿射操作得到 −2,−2,1,−2,1,3-2,-2,1,-2,1,3。将整个序列变为零后,校准仍得到全零序列。倒数第二次修改将 a6a_6 变为 −1-1,最后一次校准又将其变为 00。

数据范围与子任务

对于所有数据:

  • 1≤n,m≤1051\le n,m\le10^5;
  • 0≤ai,u,v<P0\le a_i,u,v<P;
  • 1≤l≤r≤n1\le l\le r\le n;
  • 操作一满足 1≤k≤r−l1\le k\le r-l;
  • 至少有一次操作三。

记 N=max⁡(n,m)N=\max(n,m)。

子任务 分值 附加限制
1 20 N≤1000N\le1000
2 15 没有操作一
3 包含操作一,且所有操作一均满足 k=1k=1
4 20 N≤10000N\le10000
5 30 无

各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。更多样例见附加文件 samples.zip。