洛谷P6864 [RC-03] 记忆
今日模拟赛，看见此题，苦思冥想许久，度一时辰，未果，见洛谷一番目题解与吾之胡思甚像，懊悔不已，又见矩阵线段树做法，码甚清晰，大喜，故记之。
传送门
显然有一个暴力分，如果没有 \(3\) 操作，那么简记当前的括号序列 \(\underbrace{()()() \dots ()}_{k个}\)。
如果加上操作 \(1\)，\(k \to k+1\)，对答案贡献为 \(k+1\)（因为右端为加入的括号，左端随便选）。
如果加上操作 \(2\)，\(k = 1\)，对答案贡献为 \(1\)。
这显然是 \(O(n)\) 的。
直接讲正解。
因为有了操作 \(3\)，我们构造矩阵 \(\begin{bmatrix} ans&k&1 \end{bmatrix}\)。
初始时操作序列都为单位矩阵。
操作 \(1\)，构造矩阵 \(\begin{bmatrix} 1&0&0 \\ 1&1&0 \\ 1&1&1 \end{bmatrix}\)。
操作 \(2\)，构造矩阵 \(\begin{bmatrix} 1&0&0 \\ 0&0&0 \\ 1&1&1 \end{bmatrix}\)。
对于操作 \(3\)，让矩阵在单位矩阵与操作矩阵间来回翻转就可以了。
\(\huge \mathscr{Code}\)
#include<iostream>
#include<cstring>
#define int long long
#define mem(a) memset((a),0,sizeof (a))
using namespace std;
const int N = 2e5+100;
int n,ans,x,canc[N],operate[N],rec[N];
struct Matrix{int m[4][4];friend Matrix operator *(Matrix a,Matrix b){Matrix p;memset(p.m,0,sizeof(p));for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) for(int k=1;k<=3;k++) p.m[i][j] += a.m[i][k]*b.m[k][j]; return p;}void Print_Matrix(){for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cout<<m[i][j]<<' '; }cout<<'\n';}}
};
void Normal(Matrix &p) {mem(p.m),p.m[1][1] = p.m[2][2] = p.m[3][3] = 1;}
void Op1(Matrix &p) {mem(p.m),p.m[1][1] = p.m[2][2] = p.m[3][3] = p.m[2][1] = p.m[3][1] = p.m[3][2] = 1;}
void Op2(Matrix &p) {mem(p.m),p.m[1][1] = p.m[3][1] = p.m[3][2] = p.m[3][3] = 1;}
struct node{int l,r;Matrix ans;
}T[N<<2];
void pushup(int u){T[u].ans = T[u*2].ans*T[u*2+1].ans;
}
void build(int u,int l,int r){T[u].l = l,T[u].r = r;if(l==r){Normal(T[u].ans);return;}int mid = (T[u].l+T[u].r)>>1;build(u*2,l,mid),build(u*2+1,mid+1,r);pushup(u);
}
void update(int u,int q,int op){if(T[u].l==T[u].r){op==3?Normal(T[u].ans):op==1?Op1(T[u].ans):Op2(T[u].ans);return;}int mid = (T[u].l+T[u].r)>>1;if(q<=mid) update(u*2,q,op);else update(u*2+1,q,op);pushup(u);
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;build(1,1,n);for(int i=1;i<=n;i++){rec[i] = i;cin>>operate[i];if(operate[i]==3){cin>>x;rec[i] = rec[x];canc[rec[i]] ^= 1;update(1,rec[i],canc[rec[i]]?3:operate[rec[i]]);}if(operate[i]==2) update(1,i,2);if(operate[i]==1) update(1,i,1);Matrix p;mem(p.m);p.m[1][1] = p.m[1][2] = p.m[1][3] = 1;p = p*T[1].ans;cout<<p.m[1][1]<<'\n';}return 0;
}
小结：什么时候可以想到矩阵乘法？
首先当前操作对之后的操作没有影响。
其次，操作后的贡献只取决于之前的贡献。