方方方的数据结构

题目描述

在很久很久以前,有一个长度为n的数列,一开始数列全是0。 方方方觉得这个数列太单调了,打算对它进行m次操作,每次操作为区间加法或者区间乘法。 方方方进行一些操作之后,还可能会对一段的和进行询问。 但是进行过一些操作之后,方方方可能会发现之前某次操作失误了,需要撤销这次操作,其它操作和其它操作的前后顺序保持不变。 方方方想好这些操作之后,马上想到了一个优秀的数据结构可以维护这些东西,可是他懒得写标程了,就生成了10个**随机数据**,就把这道题扔给了你。 **数据全是随机的,生成方式见最下方的提示。**

输入输出格式

输入格式


第一行两个数n、m,表示数列的长度和操作个数。 接下来m行每行2或4个数。 1. 如果第一个数为1,接下来跟三个数l、r、d,表示把区间[l,r]中的数加上d。 2. 如果第一个数为2,接下来跟三个数l、r、d,表示把区间[l,r]中的数乘上d。 3. 如果第一个数为3,接下来跟一个数p,表示询问p位置的数$mod~998244353$。 4. 如果第一个数为4,接下来跟一个数p,表示将第p行输入的操作撤销(保证为加或者乘操作,一个操作不会被撤销两次)。

输出格式


对于每个3操作输出一行表示答案。

输入输出样例

输入样例 #1

6 14
1 1 5 1
2 2 4 3
1 2 6 5
3 2
4 1
3 3
2 1 3 4
3 3
1 2 2 3
3 2
4 7
3 1
3 2
3 3

输出样例 #1

8
5
20
23
0
8
5

说明

对于20%的数据,$n,m \leq 500$,时限1s。 对于50%的数据,$n,m \leq 30000$,时限1s。 对于100%的数据,$1 \leq n,m \leq 150000$,$0 \leq p \leq 1073741823$(原因见数据生成器),时限4.5s。 数据生成器: ```cpp #include using namespace std; int rand_() {return rand()&32767;} int br() {return rand_()*32768+rand_();} vector cs; int main() { srand(...); //这里要填一个种子 int n=...,m=...; //这里要填n、m cout<r) swap(l,r); cs.push_back(i); cout<