方方方的数据结构

题目描述

在很久很久以前,有一个长度为 $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$ 位置的数 $\bmod\ 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 <bits/stdc++.h> using namespace std; int rand_() {return rand()&32767;} int br() {return rand_()*32768+rand_();} vector<int> cs; int main() { srand(...); //这里要填一个种子 int n=...,m=...; //这里要填n、m cout<<n<<" "<<m<<"\n"; for(int i=1;i<=m;i++) { int o=rand()%4+1; if(o<=2) { cout<<o<<" "; int l=br()%n+1,r=br()%n+1; if(l>r) swap(l,r); cs.push_back(i); cout<<l<<" "<<r<<" "<<br()<<"\n"; } else if(o==3) cout<<o<<" "<<br()%n+1<<"\n"; else { if(!cs.size()) {--i; continue;} int s=br()%cs.size(),g=cs[s]; cs.erase(cs.begin()+s); cout<<o<<" "<<g<<"\n"; } } } ```