LuoguP3710 方方方的数据结构

(Updated: )
oi

Description

题目链接：P3710

给定一个长度为 $n$ 的序列，一开始序列的数全是 $0$，有 $m$ 个操作。

  1. 区间加
  2. 区间乘
  3. 单点查
  4. 撤销第 $p$ 个操作（保证为加、乘操作）

$1\leq n,m\leq 150000$，时间限制 $4s$，保证数据随机。

Solution

首先如果只有前 $3$ 个操作可以使用线段树。

然后考虑第 $4$ 个操作如何转化。

由于不是强制在线，所以可以先把所有询问都先离线下来，然后从后往前扫一遍所有第 $4$ 个操作，得出每个 $1,2$ 操作的生效区间。

然后就转化成了个二维平面问题：

  1. 矩阵加
  2. 矩阵乘
  3. 单点查

由于本蒟蒻不会 KD-TREE，所以就直接用四叉树啦（虽然四叉树的复杂度貌似是假的）

然而内存限制为 128MB，所以需要先把所有询问需要使用的区间先找出来，只对这个区间修改&查询即可（这种方法只能针对于单点查询）。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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].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;
}