题解：P6864 [RC-03] 记忆

Problem

P6864
维护一个字符串 S，支持变成 (S)、变成 S() 以及撤销一次操作（保证该操作在被撤销前生效，可撤销撤销操作），求每次操作后的合法括号字串数量。

Solution

题解中大部分讲的都是矩阵

\Theta(n\log n)

的做法。但是我在模拟赛中乱搞得到一种更快的做法。
我们考虑将原字串每一对括号视为一个节点，每个节点的父亲是在原串上最小的能够包含节点代表的括号的括号对应的节点（即

u

是

v

的父亲节点，当前仅当

u

对应的括号包含

v

对应的括号，且不存在任何括号被

u

包含且包含

v

），形成一棵树。
这样，我们可以考虑树上 dp，我们记

f_u

为以

u

为根的树的答案，

son_u

代表

u

的儿子的集合，则有：

f_u=\left(\sum_{v\in son_u}f_v\right)+\frac{\lvert son_u\rvert\cdot\left(\lvert son_u\rvert+1\right)}{2}

其中前面的求和是子树内答案，后面的统计在这个括号内一层的括号的答案。可以建一个虚拟根节点方便统计答案。
考虑操作 S()，相当于自己建一个新的节点，向虚拟根节点连边。
考虑操作 (S)，可以将虚拟根节点当作这个节点，并新建一个新的虚拟根节点由该点连边。
考虑撤销操作，若该撤销使字符串少一对括号，相当于删除对应节点并将该节点所有子节点连到被删除节点处。若该撤销使字符串多一对括号（或者说恢复操作），相当于将从该店连到其父亲的子节点从其父亲中删去并连到该点上，再有该店连向其父亲。
为处理撤销操作，我们定义

g_i

代表该节点为他父节点贡献的子节点个数，则当该节点未删去时，有：

f_u=\left(\sum_{v\in son_u}f_v\right)+\frac{\sum_{v\in son_u}g_v\cdot\left(\left(\sum_{v\in son_u}g_v+1\right)\right)}{2}\\ g_u=1

当该节点删去时，有：

f_u=\sum_{v\in son_u}f_v\\ g_u=\sum_{v\in son_u}g_v

我们可以在每次修改后进行整条到根节点路径的更新。时间平均复杂度

\Theta(n\log^2n)

。

Optimization

首先，所有节点可以先将

s_u=\sum_{v\in son_u}g_v

给维护起来，这样就可以方便的删除一个节点。
其次，对于一次删除或恢复，可以先用栈维护该节点到根节点的路径，取消该路径上的贡献，更改后在恢复贡献，这样这个算法的时间平均复杂度就降到

\Theta(n\log n)

了。
此外，我们发现，没有必要对每个节点维护

f

，可以发现答案等于

\sum_{u\in T}\frac{s_u\cdot(s_u+1)}{2}

，我们可以单独维护一个答案变量。
有了上面的优化后，转移就只有

s_u=\sum_{v\in son_u}g_v\\ g_u=\begin{cases}1&\text{u isn't deleted}\\s_u&\text{u is deleted}\end{cases}

这时我们发现，当一个节点未被删除时，它子树内的删数并不会影响到这个结点的祖先（因为这个的

g

值始终为

1

）这时，我们可以将之前维护的到根节点的链改为到最近的未被删除的点即可，可以发现，这条链的期望值不会很大（大概只有

3

左右），所以在随机数据下这个做法是

\Theta(n)

的。

Code

贴上我丑陋的代码（勿喷 qwq

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
	ll x=0;
	short f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45) f=-1;
		else f=1;
		c=getchar();
	}
	while(c<58&&c>47){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10|48);
}
int Node[200005],Id=2;
int RT=1;
int alive[200005],g[200005],sg[200005],fa[200005];
ll ans=0;
int st[200005],tp;
signed main(){
	alive[1]=alive[2]=ans=g[1]=sg[1]=fa[2]=g[2]=1;
	int n=read();
	for(int i=1;i<=n;i++){
		int op=read();
		if(op==1){
			Node[i]=++Id;
			fa[Id]=RT;
			alive[Id]=1;
			g[Id]=1;
			sg[RT]++;
			ans+=sg[RT];
		}
		if(op==2){
			Node[i]=RT;
			RT=++Id;
			alive[RT]=1;
			sg[RT]=1;
			g[RT]=1;
			ans++;
			fa[Node[i]]=RT;
		}
		if(op==3){
			int x=Node[i]=-Node[read()];
			if(x<0){
				x=-x;
				//delete node x away
				st[++tp]=x;
				while(!alive[x=fa[x]])st[++tp]=x;
				for(int i=tp;i;i--){
					int o=st[i];
					sg[fa[o]]-=g[o];
					if(alive[fa[o]]){
						ans-=1ll*sg[fa[o]]*g[o]+(1ll*g[o]*(g[o]+1)>>1);
					}
					else{
						g[fa[o]]-=g[o];
					}
				}
				x=-Node[i];
				g[x]=sg[x];
				ans-=sg[x]*(sg[x]+1)>>1;
				alive[x]=0;
				for(int i=1;i<=tp;i++){
					int o=st[i];
					if(alive[fa[o]]){
						ans+=1ll*sg[fa[o]]*g[o]+(1ll*g[o]*(g[o]+1)>>1);
					}
					else{
						g[fa[o]]+=g[o];
					}
					sg[fa[o]]+=g[o];
				}
				tp=0;
			}
			else{
				//insert node x back
				st[++tp]=x;
				while(!alive[x=fa[x]])st[++tp]=x;
				for(int i=tp;i;i--){
					int o=st[i];
					sg[fa[o]]-=g[o];
					if(alive[fa[o]]){
						ans-=1ll*sg[fa[o]]*g[o]+(1ll*g[o]*(g[o]+1)>>1);
					}
					else{
						g[fa[o]]-=g[o];
					}
				}
				x=Node[i];
				alive[x]=1;
				g[x]=1;
				ans+=1ll*sg[x]*(sg[x]+1)>>1;
				for(int i=1;i<=tp;i++){
					int o=st[i];
					if(alive[fa[o]]){
						ans+=1ll*sg[fa[o]]*g[o]+(1ll*g[o]*(g[o]+1)>>1);
					}
					else{
						g[fa[o]]+=g[o];
					}
					sg[fa[o]]+=g[o];
				}
				tp=0;
			}
		}
		write(ans);putchar(10);
	}
}

Extra

我在模拟赛赛时打完了如上优化，但还是能找到 Hack 数据，可按如下方法构造：

CPP

	cout<<"200000\n";
	for(int i=1;i<=66667;i++)cout<<"2\n";
	for(int i=1;i<=66667;i++)cout<<"3 "<<66668-i<<"\n";
	for(int i=133335;i<=200000;i++)cout<<"3 "<<i-1<<"\n";

但是，这个算法在随机情况下是

\Theta(n)

的，足以高速的通过此题。

题解：P6864 [RC-03] 记忆

文章操作

Problem

Solution

Optimization

Code

Extra

相关推荐

评论

题解：P6864 [RC-03] 记忆