LuoguP3710 方方方的数据结构
yzxoi
·
·
题解
My Blog
Description
题目链接：P3710
给定一个长度为 n 的序列，一开始序列的数全是 0，有 m 个操作。
- 区间加
- 区间乘
- 单点查
- 撤销第 p 个操作（保证为加、乘操作）
## Solution
首先如果只有前 $3$ 个操作可以使用线段树。
然后考虑第 $4$ 个操作如何转化。
由于不是强制在线，所以可以先把所有询问都先离线下来，然后从后往前扫一遍所有第 $4$ 个操作，得出每个 $1,2$ 操作的生效区间。
然后就转化成了个二维平面问题：
1. 矩阵加
2. 矩阵乘
3. 单点查
由于本蒟蒻不会 KD-TREE，所以就直接用四叉树啦~~（虽然四叉树的复杂度貌似是假的）~~
然而内存限制为 128MB，所以需要先把所有询问需要使用的区间先找出来，只对这个区间修改&查询即可（这种方法只能针对于单点查询）。
## Code
```cpp
#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%10+'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].S||T[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;
}
```