QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100

# 7458. rprsvq

统计

你有一个长度为 $n$ 的序列 $v_1, v_2, \dots, v_n$,初值全都为 $0$。

你要进行 $m$ 次操作:

  • 操作 1:给出 $l,r,a$,将 $v_l,v_{l+1},\dots ,v_r$ 的值加上 $a$。
  • 操作 2:给出 $l,r$,求在$v_l,v_{l+1}, \dots ,v_r$ 中选出一个非空的子序列,求所有方案中选出的子序列的方差之和,答案对 $998244353$ 取模。

一个序列 $a_1,a_2, \dots, a_n$ 的方差定义为令 $\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$,则方差为 $\frac{1}{n}\sum_{i=1}^n (a_i-\bar{a})^2$。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行,每行有四个整数 $1~l~r~a$ 或三个整数 $2~l~r$,表示第一类或第二类操作,保证 $0\leq a< 998244353$。

输出格式

对每个第二类操作,输出一行表示答案。

样例数据

样例 1 输入

4 4
1 2 4 1
2 1 3
1 1 2 2
2 1 4

样例 1 输出

388206138
339680376

样例 1 解释

对于第一个测试数据的第一个询问,序列是 $\{0,1,1\}$,所有的子序列中只有 $\{0,1\}, \{0,1\}$ 和 $\{0,1,1\}$ 方差不为 $0$,分别是 $\frac{1}{4}, \frac{1}{4}, \frac{2}{9}$,总和为 $\frac{13}{18}$。

样例 2 输入

10 20
1 4 4 520968631
1 4 7 988452236
1 4 9 355405133
2 9 10
2 2 8
1 3 5 400339337
2 3 8
2 6 7
2 4 10
2 7 9
1 3 8 387471594
1 2 4 559944503
2 1 8
1 4 7 108832063
2 5 9
2 4 8
1 3 8 622785003
2 9 10
1 2 7 252591713
1 5 6 666406180

样例 2 输出

570099967
274921471
285269733
0
571283655
970723747
401326984
17519114
844628984
570099967

子任务

Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078

对于 $10\%$ 的数据,$n\leq 10, m\leq 1000$。

对于 $20\%$ 的数据,$n\leq 16, m\leq 1000$。

对于 $30\%$ 的数据,$n\leq 100, m\leq 10^3$。

对于 $50\%$ 的数据,$n, m\leq 10^3$。

对于另外$10\%$的数据,$n\leq 10^5$,保证首先是第一类操作,然后是第二类操作。

对于 $80\%$ 的数据,$n, m\leq 10^5$。

对于 $100\%$ 的数据,$1\leq n \leq 5\times 10^6,1\leq m\leq 10^5$。