先考虑没有 \(3\) 操作该怎么做。
对于当前字符串把其分成多组互不包含的括号的形式，即 \((\cdots)()()\) 这样，考虑经过 \(1 / 2\) 操作后对互不包含的括号组数 \(b\) 和答案 \(v\) 会产生什么影响。
- \(1\) 操作，加上过后便会多上一组互不包含的括号，\(b\leftarrow b' + 1\)，同时这个括号能和前面的所有互不包含的括号连起来对答案产生贡献，\(v\leftarrow v' + b' + 1\)。
- \(2\) 操作，此时所有括号都被新的括号包含了，\(b = 1\)，答案会多上整个串，\(v\leftarrow v' + 1\)。
再来考虑有 \(3\) 操作该怎么做，这个操作即可以改变一个操作对答案是否产生贡献，每次进行此操作都需要重头再推，考虑降低修改的时间复杂度。
单点修改全局查询，考虑到使用线段树，再结合 \(v, b\) 能发现其变化都是 \(\times +\) 操作，考虑把其写成矩阵的形式 \(\begin{bmatrix}v & b & 1\end{bmatrix}\)，再来考虑构造每个操作对应的矩阵。
- \(1\) 操作：\(\begin{bmatrix}v & b & 1\end{bmatrix} \times\begin{bmatrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}= \begin{bmatrix}v + b + 1 & b + 1 & 1\end{bmatrix}\)。
- \(2\) 操作：\(\begin{bmatrix}v & b & 1\end{bmatrix} \times\begin{bmatrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1 \end{bmatrix}= \begin{bmatrix}v + 1 & 1 & 1\end{bmatrix}\)。
- \(3\) 操作：如果是被删除的操作还原按照 \(1 / 2\) 操作构造即可，若是删除则为单位矩阵，即 \(\begin{bmatrix}v & b & 1\end{bmatrix} \times\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}= \begin{bmatrix}v & b & 1\end{bmatrix}\)。
对于每个操作，直接单点修改对应位置的矩阵即可，最后用初始矩阵 \(\begin{bmatrix}1 & 1 & 1\end{bmatrix}\) 乘上全部的操作矩阵的乘积即可。
时间复杂度 \(\mathcal{O}(w^3\times n\log n)\)，\(w\) 为矩阵大小。
#include<bits/stdc++.h>
using ll = long long;
const int N = 2e5 + 10;
int n;
struct Matrix {
ll a[3][3];
Matrix() {
memset(a, 0, sizeof(a));
}
const ll* operator [] (int x) const {
return a[x];
}
ll* operator [] (int x) {
return a[x];
}
Matrix operator * (const Matrix &b) const {
Matrix c;
for (int i = 0; i < 3; i++) {
for (int k = 0; k < 3; k++) {
for (int j = 0; j < 3; j++) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
return c;
}
Matrix operator *= (const Matrix &b) {
return *this = *this * b;
}
};
Matrix t[N * 4];
void pushup(int k) {
t[k] = t[k << 1] * t[k << 1 | 1];
}
void build(int k = 1, int l = 1, int r = n) {
if (l == r) {
t[k][0][0] = t[k][1][1] = t[k][2][2] = 1;
return ;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
pushup(k);
}
void update(int x, const Matrix &y, int k = 1, int l = 1, int r = n) {
if (l == r) {
t[k] = y;
return ;
}
int mid = (l + r) >> 1;
if (x <= mid) {
update(x, y, k << 1, l, mid);
} else {
update(x, y, k << 1 | 1, mid + 1, r);
}
pushup(k);
}
int opt[N], x[N], vis[N];
void make_matrix(int opt, Matrix &z) {
if (opt == 0) {
z[0][0] = z[1][1] = z[2][2] = 1;
} else if (opt == 1) {
z[0][0] = z[1][0] = z[1][1] = z[2][0] = z[2][1] = z[2][2] = 1;
} else if (opt == 2) {
z[0][0] = z[2][0] = z[2][1] = z[2][2] = 1;
}
}
int main() {
scanf("%d", &n);
build();
for (int i = 1; i <= n; i++) {
scanf("%d", &opt[i]);
if (opt[i] != 3) {
Matrix z;
make_matrix(opt[i], z);
update(i, z);
} else if (opt[i] == 2) {
Matrix z;
z[0][0] = z[2][0] = z[2][1] = z[2][2] = 1;
update(i, z);
} else {
scanf("%d", &x[i]);
if (opt[x[i]] == 3) {
x[i] = x[x[i]];
}
vis[x[i]] ^= 1;
Matrix z;
make_matrix(vis[x[i]] ? 0 : opt[x[i]], z);
update(x[i], z);
}
Matrix x;
x[0][0] = x[0][1] = x[0][2] = 1;
x *= t[1];
printf("%lld\n", x[0][0]);
}
return 0;
}