P9753 [CSP-S 2023] 消消乐 题解

· · 题解

暴力做法。

首先考虑判断一个串能否被删空，「删除相邻相同字符」等价于不区分左右括号的括号匹配。维护一个栈，从前到后遍历整个串，如果当前字符和栈顶相同就弹栈，不同就压入。如果最后栈是空的说明这个串是可消除的。

观察发现栈是可拼接的。具体的，有字符串 A 和字符串 B。字符串 A 从后向前进行上述过程后的栈为 C，字符串 B 从前向后进行上述过程后的栈为 D。若 C=D，则字符串 A 后面拼上字符串 B 得到的串一定是可删除的。原因是处理后的栈一定无法进行内部匹配，只能两个栈对应位置两两匹配。

考虑分治。设当前分治区间为 [L,R]，左区间为 [L,mid]，右区间为 [mid+1,R]，区间长度 len=R-L+1，需要处理跨过中心点的可消除区间个数。

栈信息可以看成一个字符串，左区间和右区间各有 O(len) 个字符串，问题转化为计算有多少对左右字符串相同。

可以通过先处理出左区间的信息，然后对于右区间的每个字符串，查找左区间有多少个与其相同。

观察到「弹栈」和「压入」都只会使得字符串的末尾变化一位。所以可以建出 Trie 树，记录当前位置，「弹栈」即跳到父亲，「压入」即跳到对应儿子。

左区间跳到一个位置就把这个位置加一，右区间跳到一个位置答案就加上这个位置的值。

清空的时候要尤其注意细节，时间复杂度不要带上字符集。

精细实现下对于一个区间的时间复杂度为 O(len)，总时间复杂度 O(n\log n)，空间复杂度 n|S|。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<ctime>
#include<random>
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=2e6+10;
const int M=26;
int n,m,a[N],b[N],fa[N],siz[N],st[N],top,p,to[N][M];
char str[N];
ll ans;
void ins(int x){
    if(to[p][x]){
        p=to[p][x];
        return;
    }
    m++;
    b[m]=x;
    fa[m]=p;
    to[p][x]=m;
    p=m;
}
void add(int x){
    if(to[p][x]){
        p=to[p][x];
        return;
    }
    m++;
    b[m]=x;
    fa[m]=p;
    to[p][x]=m;
    p=m;
}
void init(){
    for(int i=1;i<=m;i++){
        to[fa[i]][b[i]]=0;
        fa[i]=b[i]=siz[i]=0;
    }
}
void solve(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    solve(l,mid);
    solve(mid+1,r);
    m=1,p=1;
    top=0;
    for(int i=mid;i>=l;i--){
        int fl=1;
        if(top){
            if(a[i]==st[top]){
                fl=0;
                top--;
            }   
            else st[++top]=a[i];
        }
        else st[++top]=a[i];
        if(fl)ins(a[i]);
        else p=fa[p];
        siz[p]++;
    }
    top=0;
    p=1;
    for(int i=mid+1;i<=r;i++){
        int fl=1;
        if(top){
            if(a[i]==st[top]){
                fl=0;
                top--;
            }   
            else st[++top]=a[i];
        }
        else st[++top]=a[i];
        if(fl)add(a[i]);
        else p=fa[p];
        ans+=siz[p];
    }
    init();
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n=read();
    scanf("%s",str+1);
    for(int i=1;i<=n;i++)
        a[i]=str[i]-'a';
    solve(1,n);
    cout<<ans;
    return 0;
}