#P3710. 方方方的数据结构

    ID: 4987 远端评测题 4500ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>线段树平衡树洛谷原创O2优化枚举,暴力块状链表,块状数组,分块洛谷月赛

方方方的数据结构

题目描述

在很久很久以前,有一个长度为 nn 的数列,一开始数列全是 00

方方方觉得这个数列太单调了,打算对它进行 mm 次操作,每次操作为区间加法或者区间乘法。

方方方进行一些操作之后,还可能会对一段的和进行询问。

但是进行过一些操作之后,方方方可能会发现之前某次操作失误了,需要撤销这次操作,其它操作和其它操作的前后顺序保持不变。

方方方想好这些操作之后,马上想到了一个优秀的数据结构可以维护这些东西,可是他懒得写标程了,就生成了 1010随机数据,就把这道题扔给了你。

数据全是随机的,生成方式见最下方的提示。

输入格式

第一行两个数 n,mn,m,表示数列的长度和操作个数。

接下来 mm 行每行 2244 个数。

  1. 如果第一个数为 11,接下来跟三个数 l,r,dl,r,d,表示把区间 [l,r][l,r] 中的数加上 dd
  2. 如果第一个数为 22,接下来跟三个数 l,r,dl,r,d,表示把区间 [l,r][l,r] 中的数乘上 dd
  3. 如果第一个数为 33,接下来跟一个数 pp,表示询问 pp 位置的数 mod 998244353\bmod\ 998244353
  4. 如果第一个数为 44,接下来跟一个数 pp,表示将第 pp 行输入的操作撤销(保证为加或者乘操作,一个操作不会被撤销两次)。

输出格式

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

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
8
5
20
23
0
8
5

提示

对于 20%20\% 的数据,n,m500n,m \leq 500,时限1s。

对于 50%50\% 的数据,n,m30000n,m \leq 30000,时限1s。

对于 100%100\% 的数据,1n,m1500001 \leq n,m \leq 1500000p10737418230 \leq p \leq 1073741823(原因见数据生成器),时限4.5s。

数据生成器:

#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";
        }
    }
}