方方方的数据结构 ,一道有趣的题目，可以用 分块、k-D Tree、四分树 多种解法解决的题。
出题人 fjzzq2002。
题目链接：Luogu P3710。
未完待续
题目
题目描述
在很久很久以前，有一个长度为 \(n\) 的数列，一开始数列全是 \(0\)。
方方方觉得这个数列太单调了，打算对它进行 \(m\) 次操作，每次操作为区间加法或者区间乘法。
方方方进行一些操作之后，还可能会对一段的和进行询问。
但是进行过一些操作之后，方方方可能会发现之前某次操作失误了，需要撤销这次操作，其它操作和其它操作的前后顺序保持不变。
方方方想好这些操作之后，马上想到了一个优秀的数据结构可以维护这些东西，可是他懒得写标程了，就生成了 \(10\) 个随机数据，就把这道题扔给了你。
数据全是随机的，生成方式见数据生成器。
数据生成器：
#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";
}
}
}
数据范围&时空限制
对于 \(20\%\) 的数据，\(n,m\leq 500\)，时限 \(1\texttt{s}\)。
对于 \(50\%\) 的数据，\(n,m\leq 30000\)，时限 \(1\texttt{s}\)。
对于 \(100\%\) 的数据，\(1\leq n,m\leq 150000\)，\(0\leq p\leq 1073741823\) （原因见数据生成器），时限 \(4.5\texttt{s}\)。
题解
思路
四分树简单题。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=1.5e5+5;
const int MAXM=1.5e5+5;
const int p=998244353;
namespace SegmentTree{
#define mid1 ( ( (l1) + (r1) ) >> 1 )
#define mid2 ( ( (l2) + (r2) ) >> 1 )
const int MAXSIZE=30*MAXN;
struct Node{
int son[2][2];
int tagA,tagM;
#define son(x) unit[(x)].son
#define tagA(x) unit[(x)].tagA
#define tagM(x) unit[(x)].tagM
};
Node unit[MAXSIZE];
int tot;
inline void build(reg int &k,const int& l1,const int& r1,const int& l2,const int& r2,const int& u,const int& v){
if(l1>r1||l2>r2)
return;
if(!k)
tagM(k=++tot)=1;
if(l1==r1&&l2==r2)
return;
if(u<=mid1)
if(v<=mid2)
build(son(k)[0][0],l1,mid1,l2,mid2,u,v);
else
build(son(k)[0][1],l1,mid1,mid2+1,r2,u,v);
else
if(v<=mid2)
build(son(k)[1][0],mid1+1,r1,l2,mid2,u,v);
else
build(son(k)[1][1],mid1+1,r1,mid2+1,r2,u,v);
return;
}
inline int add(reg int a,reg int b){
reg int sum=a+b;
return sum>=p?sum-p:sum;
}
inline void Add(const int& k,const int& Val){
tagA(k)=add(tagA(k),Val);
return;
}
inline int mul(reg int a,reg int b){
return 1ll*a*b%p;
}
inline void Mul(const int& k,const int& Val){
tagA(k)=mul(tagA(k),Val);
tagM(k)=mul(tagM(k),Val);
return;
}
inline void pushdown(reg int k){
if(tagM(k)!=1){
if(son(k)[0][0])Mul(son(k)[0][0],tagM(k));
if(son(k)[0][1])Mul(son(k)[0][1],tagM(k));
if(son(k)[1][0])Mul(son(k)[1][0],tagM(k));
if(son(k)[1][1])Mul(son(k)[1][1],tagM(k));
tagM(k)=1;
}
if(tagA(k)){
if(son(k)[0][0])Add(son(k)[0][0],tagA(k));
if(son(k)[0][1])Add(son(k)[0][1],tagA(k));
if(son(k)[1][0])Add(son(k)[1][0],tagA(k));
if(son(k)[1][1])Add(son(k)[1][1],tagA(k));
tagA(k)=0;
}
return;
}
inline void updateAdd(const int& k,const int& l1,const int& r1,const int& l2,const int& r2,const int& L1,const int& R1,const int& L2,const int& R2,const int& Val){
if(!k)
return;
if(L1<=l1&&r1<=R1&&L2<=l2&&r2<=R2){
Add(k,Val);
return;
}
pushdown(k);
if(L1<=mid1){
if(L2<=mid2)
updateAdd(son(k)[0][0],l1,mid1,l2,mid2,L1,R1,L2,R2,Val);
if(R2>mid2)
updateAdd(son(k)[0][1],l1,mid1,mid2+1,r2,L1,R1,L2,R2,Val);
}
if(R1>mid1){
if(L2<=mid2)
updateAdd(son(k)[1][0],mid1+1,r1,l2,mid2,L1,R1,L2,R2,Val);
if(R2>mid2)
updateAdd(son(k)[1][1],mid1+1,r1,mid2+1,r2,L1,R1,L2,R2,Val);
}
return;
}
inline void updateMul(const int& k,const int& l1,const int& r1,const int& l2,const int& r2,const int& L1,const int& R1,const int& L2,const int& R2,const int& Val){
if(!k)
return;
if(L1<=l1&&r1<=R1&&L2<=l2&&r2<=R2){
Mul(k,Val);
return;
}
pushdown(k);
if(L1<=mid1){
if(L2<=mid2)
updateMul(son(k)[0][0],l1,mid1,l2,mid2,L1,R1,L2,R2,Val);
if(R2>mid2)
updateMul(son(k)[0][1],l1,mid1,mid2+1,r2,L1,R1,L2,R2,Val);
}
if(R1>mid1){
if(L2<=mid2)
updateMul(son(k)[1][0],mid1+1,r1,l2,mid2,L1,R1,L2,R2,Val);
if(R2>mid2)
updateMul(son(k)[1][1],mid1+1,r1,mid2+1,r2,L1,R1,L2,R2,Val);
}
return;
}
inline int query(reg int k,reg int l1,reg int r1,reg int l2,reg int r2,reg int u,reg int v){
while(true){
if(!k)
return 0;
if(l1==r1&&l2==r2)
return tagA(k);
pushdown(k);
if(u<=mid1)
if(v<=mid2)
k=son(k)[0][0],r1=mid1,r2=mid2;
else
k=son(k)[0][1],r1=mid1,l2=mid2+1;
else
if(v<=mid2)
k=son(k)[1][0],l1=mid1+1,r2=mid2;
else
k=son(k)[1][1],l1=mid1+1,l2=mid2+1;
}
}
}
int n,m;
int t[MAXM];
struct updates{
int opt,l,r,d,st,ed;
};
struct querys{
int u,v;
};
updates U[MAXM];
querys Q[MAXM];
int id[MAXM];
int main(void){
n=read(),m=read();
reg int cntU=0,cntQ=0;
reg int tim=0;
reg bool flag=false;
for(reg int i=1;i<=m;++i){
static int opt,u;
opt=read();
switch(opt){
case 1:case 2:{
flag=false;
id[i]=++cntU;
U[cntU].opt=opt;
U[cntU].l=read(),U[cntU].r=read(),U[cntU].d=read();
U[cntU].st=tim+1,U[cntU].ed=m;
break;
}
case 3:{
if(!flag)
++tim;
Q[++cntQ].v=tim;
Q[cntQ].u=read();
flag=true;
break;
}
case 4:{
flag=false;
u=read();
U[id[u]].ed=tim;
break;
}
}
}
for(reg int i=1;i<=cntU;++i)
if(U[i].ed>tim)
U[i].ed=tim;
int root=0;
for(reg int i=1;i<=cntQ;++i)
SegmentTree::build(root,1,n,1,tim,Q[i].u,Q[i].v);
reg int ptr=1;
for(reg int i=1;i<=cntQ;++i){
while(ptr<=cntU&&U[ptr].st<=Q[i].v){
if(U[ptr].st<=U[ptr].ed){
if(U[ptr].opt==1)
SegmentTree::updateAdd(root,1,n,1,tim,U[ptr].l,U[ptr].r,U[ptr].st,U[ptr].ed,U[ptr].d);
else
SegmentTree::updateMul(root,1,n,1,tim,U[ptr].l,U[ptr].r,U[ptr].st,U[ptr].ed,U[ptr].d);
}
++ptr;
}
printf("%d\n",SegmentTree::query(root,1,n,1,tim,Q[i].u,Q[i].v));
}
return 0;
}
近期评论