LuoguP3710 方方方的数据结构
Description
题目链接：P3710
给定一个长度为 n 的序列，一开始序列的数全是 0，有 m 个操作。
- 区间加
- 区间乘
- 单点查
- 撤销第 p 个操作（保证为加、乘操作）
1leq n,mleq 150000，时间限制 4s，保证数据随机。
Solution
首先如果只有前 3 个操作可以使用线段树。
然后考虑第 4 个操作如何转化。
由于不是强制在线，所以可以先把所有询问都先离线下来，然后从后往前扫一遍所有第 4 个操作，得出每个 1,2 操作的生效区间。
然后就转化成了个二维平面问题：
- 矩阵加
- 矩阵乘
- 单点查
由于本蒟蒻不会 KD-TREE，所以就直接用四叉树啦（虽然四叉树的复杂度貌似是假的）
然而内存限制为 128MB，所以需要先把所有询问需要使用的区间先找出来，只对这个区间修改&查询即可（这种方法只能针对于单点查询）。
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=150010,P=998244353;
int n,m,A[N],rt;
struct Que{int opt,l,r,x;}q[N];
class SegmentTree{
private:
int cnt;
struct node{int son[4],S,T,sz;}T[N*20];//由于每个询问最多只能扫log的区间，所以只需要开 N*20，S维护和，T为乘懒标记
#define midX (a c>>1)
#define midY (b d>>1)
#define S0 T[x].son[0],a,b,midX,midY
#define S1 T[x].son[1],midX 1,b,c,midY
#define S2 T[x].son[2],a,midY 1,midX,d
#define S3 T[x].son[3],midX 1,midY 1,c,d
I void NW(int& x,CI a,CI b,CI c,CI d){!x&&(T[x= cnt].sz=(c-a 1)*(d-b 1),
T[x].T=1,T[x].S=T[x].son[0]=T[x].son[1]=T[x].son[2]=T[x].son[3]=0);}
#define PD(x,a,b,c,d) (x&&T[x].sz>1&&(T[x].ST[x].T>1)&&(
T[x].son[0]&&(T[T[x].son[0]].T=1LL*T[T[x].son[0]].T*T[x].T%P,T[T[x].son[0]].S=1LL*T[T[x].son[0]].S*T[x].T%P,(T[T[x].son[0]].S =T[x].S)%=P,0),
T[x].son[1]&&(T[T[x].son[1]].T=1LL*T[T[x].son[1]].T*T[x].T%P,T[T[x].son[1]].S=1LL*T[T[x].son[1]].S*T[x].T%P,(T[T[x].son[1]].S =T[x].S)%=P,0),
T[x].son[2]&&(T[T[x].son[2]].T=1LL*T[T[x].son[2]].T*T[x].T%P,T[T[x].son[2]].S=1LL*T[T[x].son[2]].S*T[x].T%P,(T[T[x].son[2]].S =T[x].S)%=P,0),
T[x].son[3]&&(T[T[x].son[3]].T=1LL*T[T[x].son[3]].T*T[x].T%P,T[T[x].son[3]].S=1LL*T[T[x].son[3]].S*T[x].T%P,(T[T[x].son[3]].S =T[x].S)%=P,0),
T[x].S=0,T[x].T=1))
public:
I void B(int& x,CI a,CI b,CI c,CI d,CI Qx,CI Qy){//预先建点
NW(x,a,b,c,d);if(a==c&&b==d) return ;
Qx<=midX&&Qy<=midY&&(B(S0,Qx,Qy),0),
Qx>midX&&Qy<=midY&&(B(S1,Qx,Qy),0),
Qx<=midX&&Qy>midY&&(B(S2,Qx,Qy),0),
Qx>midX&&Qy>midY&&(B(S3,Qx,Qy),0);
}
I void Add(int& x,CI a,CI b,CI c,CI d,CI Qa,CI Qb,CI Qc,CI Qd,CI v){//矩阵加
if(!x) return ;if(Qa<=a&&Qb<=b&&c<=Qc&&d<=Qd) return void((T[x].S =v)%=P);
PD(x,a,b,c,d),Qa<=midX&&Qb<=midY&&(Add(S0,Qa,Qb,min(Qc,midX),min(Qd,midY),v),0),
Qc>midX&&Qb<=midY&&(Add(S1,max(Qa,midX 1),Qb,Qc,min(Qd,midY),v),0),
Qa<=midX&&Qd>midY&&(Add(S2,Qa,max(Qb,midY 1),min(Qc,midX),Qd,v),0),
Qc>midX&&Qd>midY&&(Add(S3,max(Qa,midX 1),max(Qb,midY 1),Qc,Qd,v),0);
}
I void Mul(int& x,CI a,CI b,CI c,CI d,CI Qa,CI Qb,CI Qc,CI Qd,CI v){//矩阵乘
if(!x) return ;if(Qa<=a&&Qb<=b&&c<=Qc&&d<=Qd) return T[x].T=1LL*T[x].T*v%P,void(T[x].S=1LL*T[x].S*v%P);
PD(x,a,b,c,d),Qa<=midX&&Qb<=midY&&(Mul(S0,Qa,Qb,min(Qc,midX),min(Qd,midY),v),0),
Qc>midX&&Qb<=midY&&(Mul(S1,max(Qa,midX 1),Qb,Qc,min(Qd,midY),v),0),
Qa<=midX&&Qd>midY&&(Mul(S2,Qa,max(Qb,midY 1),min(Qc,midX),Qd,v),0),
Qc>midX&&Qd>midY&&(Mul(S3,max(Qa,midX 1),max(Qb,midY 1),Qc,Qd,v),0);
}
I int Q(int &x,CI a,CI b,CI c,CI d,CI Qx,CI Qy){//单点查
if(!x) return 0;if(a==c&&b==d) return T[x].S;
RI S=0;return PD(x,a,b,c,d),Qx<=midX&&Qy<=midY&&((S =Q(S0,Qx,Qy))%=P),
Qx>midX&&Qy<=midY&&((S =Q(S1,Qx,Qy))%=P),
Qx<=midX&&Qy>midY&&((S =Q(S2,Qx,Qy))%=P),
Qx>midX&&Qy>midY&&((S =Q(S3,Qx,Qy))%=P),S;
}
}S;
int main(){
RI i;for(read(n,m),i=1;i<=m;i ) read(q[i].opt),q[i].opt<=2&&(read(q[i].l,q[i].r),0),read(q[i].x),A[i]=m;
for(i=m;i>=1;i--) q[i].opt==4&&(A[q[i].x]=i);//先找出每个修改操作的生效区间
for(i=1;i<=m;i ) if(q[i].opt==3) S.B(rt,1,1,m,n,i,q[i].x);//预先建点
for(i=1;i<=m;i ) if(q[i].opt==1) S.Add(rt,1,1,m,n,i,q[i].l,A[i],q[i].r,q[i].x);
else if(q[i].opt==2) S.Mul(rt,1,1,m,n,i,q[i].l,A[i],q[i].r,q[i].x);
else if(q[i].opt==3) writeln(S.Q(rt,1,1,m,n,i,q[i].x));return 0;
}
