方方方的数据结构 ,一道有趣的题目,可以用 分块、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; }
近期评论