prologue
今天模拟赛 T3，一道很好的题目。
analysis
对于这个题目我们可以通过对操作的手玩，得出一个结论。
记 \(ans\) 为当前所有的合法子串数量，记 \(tmp\) 为当前以最后以一个括号结尾的子串个数。可以推出来前两个操作分别的转移式子：
\[ans \gets ans + tmp + 1,p \gets p + 1 \]\[ans \gets ans + 1, p \gets 1 \]感觉这个证明起来其实很显然，读者自证不难简单证明一下：
-
如果是操作 1，我们在最后面加上一个合法的匹配括号，就相当于是在继承了父亲（上一个状态）的条件下，又多了一对括号。所以得出来第一个式子。
-
如果是操作2，我们在当前的串加上一个最外层的括号。这相当于是自断一臂，因为我们此时再去统计以最后一个括号为结尾的子串，就只有前面这一坨了（傻鱼的量词是跟初中历史老师学的），我们最后的 \(ans\) 也就仅仅只是加上了前面这一整串这个答案，所以推出来第二个式子。（其实你可以看成二号操作是对前面的串进行了整个的封装。）
然后我们开始考虑怎么去维护上面两个操作。
我们上面的式子是非常具有矩阵转移的性质的，即我们可以构造这样一个 \(\begin{bmatrix}ans, tmp, 1\end{bmatrix}\) 的答案矩阵，那么我们上面两个操作的矩阵也就可以构造出来了
-
操作一的转移矩阵： \(\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1\end{bmatrix}\)
-
操作二的转移矩阵：\(\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1\end{bmatrix}\)
但是我们不可能对于每一次操作都 \(O(n)\) 扫一遍，而且还有单点修改，还要滚回去撤销操作，所以我们再考虑：
我们知道矩阵乘法是具有结合律的，即 \(A_1 A_2 A_3 = A_1(A_2 A_3)\) 所以我们的答案矩阵只需要左乘一次后面整体矩阵的乘积就好了。
我们就可以用线段树来进行这个单点修改，区间查询（查询后面所有操作的乘积）的操作。（单位矩阵对于矩阵乘法没有贡献所以我们就可以那这个当作我们的初始值了）
我们上面两个操作的思路就呼之欲出了，再考虑我们的撤销操作。
我们通过分析样例可以知道，我们的撤销操作是可以撤销之前的撤销操作的。所以我们对于一个地方的修改不可能是真的就给撤销没了，我们就可以考虑每个操作节点维护两个矩阵，一个单位矩阵 \(B\) 一个贡献矩阵 \(A\) 每次撤销操作就是 \(swap(A, B)\) 的过程。
而对于这个撤销撤销操作不就是找到自己的爹的爹么，可以用并查集来维护。（这里加粗是为了方便断句）
分析至此，接下来就是我们的代码实现了。
code time
火车头自跳。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define fom(i, a) for(rl i=a; i; -- i)
#define foa(i, a, b) for(rl i=a; i < b; ++ i)
#define fos(i, a, b) for(rl i=a; i <= b; ++ i)
#define fop(i, a, b) for(rl i=a; i >= b; -- i)
namespace IO
{
int pp1=-1; const int pp2=(1<<21)-1; char buf[1<<21],*p1=buf,*p2=buf,buffer[1<<21];
inline void flush() {fwrite(buffer,1,pp1+1,stdout); pp1=-1;}
inline void pc(const char ch) {if(pp1==pp2) flush(); buffer[++pp1]=ch;}
inline char gc(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
template <class T> inline void read(T &res){char ch=gc();bool f=0;res=0; for(;!isdigit(ch);ch=gc()) f|=ch=='-'; for(;isdigit(ch);ch=gc()) res=(res<<1)+(res<<3)+(ch^48); res=f?~res+1:res;}
template <class T> inline void ww(T x) { if(!x) pc('0'); else { static int stk[21]; int top = 0; if(x<0) pc('-'),x=~x+1; while(x) stk[top++]=x%10, x/=10; while(top--) pc(stk[top]^48);}}
}
#define wp IO::pc(' ')
#define wl IO::pc('\n')
#define ww(x) IO::ww(x)
#define read(x) IO::read(x)
#define flush() IO::flush()
constexpr ll N = 2e5 + 10;
ll n, p[N];
struct Matrix
{
ll a[4][4];
Matrix () { memset(a, 0, sizeof a);}
inline void make_I() { fos(i, 1, 3) a[i][i] = 1; }
inline void init() { fos(i, 1, 3) a[1][i] = 1; }
Matrix operator *(const Matrix &x) const
{
Matrix res;
fos(i, 1, 3) fos(k, 1, 3) fos(j, 1, 3)
res.a[i][j] += a[i][k] * x.a[k][j];
return res;
}
inline void print()
{
fos(i, 1, 3)
{
fos(j, 1, 3) ww(a[i][j]), wp;
wl;
}
}
} I, Op1, Op2, ans;
struct tree
{
ll l, r;
Matrix A, B;
} tr[N << 2];
inline ll find(ll x) { return p[x] == x ? x : p[x] = find(p[x]); }
inline void pushup(ll u) { tr[u].A = tr[u << 1].A * tr[u << 1 | 1].A; }
inline void build(ll u, ll l, ll r)
{
tr[u] = {l, r, I, I};
if(l == r) return ;
ll mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
inline void update(ll u, ll x, ll op)
{
if(tr[u].l == tr[u].r && tr[u].l == x)
{
if(op == 1) tr[u].A = Op1;
if(op == 2) tr[u].A = Op2;
return ;
}
ll mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) update(u << 1, x, op);
if(x > mid) update(u << 1 | 1, x, op);
pushup(u);
}
inline void remove(ll u, ll x)
{
if(tr[u].l == x && tr[u].r == x)
{
swap(tr[u].A, tr[u].B);
return;
}
ll mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) remove(u << 1, x);
if(x > mid) remove(u << 1 | 1, x);
pushup(u);
}
int main()
{
// freopen("dydy.in", "r", stdin), freopen("dydy.out", "w", stdout);
read(n); I.make_I(), Op1.make_I(), Op2.make_I();
fos(i, 1, n) p[i] = i;
Op2.a[2][2] = 0;
Op1.a[2][1] = Op1.a[3][1] = Op1.a[3][2] = Op2.a[3][2] = Op2.a[3][1] = 1;
build(1, 1, n);
fos(i, 1, n)
{
ans.init();
ll op, x; read(op);
if(op == 1 || op == 2) update(1, i, op);
else { read(x); remove(1, find(x)); p[i] = x; }
ans = ans * tr[1].A;
ww(ans.a[1][1]), wl;
}
flush(); return 0;
}