#P3710. 方方方的数据结构
方方方的数据结构
题目描述
在很久很久以前,有一个长度为 的数列,一开始数列全是 。
方方方觉得这个数列太单调了,打算对它进行 次操作,每次操作为区间加法或者区间乘法。
方方方进行一些操作之后,还可能会对一段的和进行询问。
但是进行过一些操作之后,方方方可能会发现之前某次操作失误了,需要撤销这次操作,其它操作和其它操作的前后顺序保持不变。
方方方想好这些操作之后,马上想到了一个优秀的数据结构可以维护这些东西,可是他懒得写标程了,就生成了 个随机数据,就把这道题扔给了你。
数据全是随机的,生成方式见最下方的提示。
输入格式
第一行两个数 ,表示数列的长度和操作个数。
接下来 行每行 或 个数。
- 如果第一个数为 ,接下来跟三个数 ,表示把区间 中的数加上 。
- 如果第一个数为 ,接下来跟三个数 ,表示把区间 中的数乘上 。
- 如果第一个数为 ,接下来跟一个数 ,表示询问 位置的数 。
- 如果第一个数为 ,接下来跟一个数 ,表示将第 行输入的操作撤销(保证为加或者乘操作,一个操作不会被撤销两次)。
输出格式
对于每个 操作输出一行表示答案。
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
提示
对于 的数据,,时限1s。
对于 的数据,,时限1s。
对于 的数据,,(原因见数据生成器),时限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";
}
}
}