P9753

lsj2009 · 2023-10-23 16:41:34 · 题解

闲话

赛时想到了括号匹配和哈希，就是没想到 [l,r]=[1,r]-[1,l-1]，遗憾离场。/fn

Problem

link：https://www.luogu.com.cn/problem/P9753。

Solution

首先考虑一个串可以被消除时的结构：

• 若 \textbf{A} 和 \textbf{B} 均可以被消除，则 \textbf{AB} 也可以被消除。
• 若 \textbf{A} 可以被消除，则 \textbf{xAx} 也可以被消除。

观察到这个东西跟“合法括号序列”的定义很像，所以我们考虑枚举左端点，然后移动右端点，开个栈去膜你，就得到了一个 \Theta(n^2) 的做法。

进一步的，考虑我们固定左端点为 1，当右端点移动到 k 时，当前栈里元素为 S；当右端点移动到 k' 时，栈里元素再一次变成 S。那么说明了什么？也就是说，[k+1,k'] 范围内的字符串被完全消除了。

但其实这样子讲也不是很准确。

比如：字符串为 \text{aaa}，S_3=S_1=\text{a}，但是在我们膜你过程中，第 2 个 \text{a} 明明是和第 1 个 \text{a} 消除了，但是在我们的意思中，他似乎是和第 3 个 \text{a} 消除了，这样子不会多记/少记吗？

实际上并不会。感性理解一下，如果说我们加入了几个字符，把原来栈顶的几个元素给消掉了，那么我们要再加入几个字符，使得加入后得到的新栈和原来栈相等，那说明了什么？说明了加入的几个字符和消掉的几个字符是相等的。也就是新加入的所有字符可以互相抵消。

那么我们时时维护一个栈，每加入一个字符后计算一下其哈希值（可以时时维护），然后丢到一个 map 里，并且查一下 map 里有几个跟他相同的。

然后就做完了，复杂度 \Theta(n\log{n})，如果用 unordered_map 代替 map，理论上可以做到 \Theta(n)。

Code

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=3e6+5,m=3e6;
const ull base=1145141;
ull p[N];
char t[N];
void init() {
    p[0]=1;
    rep(i,1,m)
        p[i]=p[i-1]*base;
}
map<ull,int> cnt;
signed main() {
    init();
    int n;
    scanf("%d",&n);
    scanf("%s",t+1);
    stack<char> s; ++cnt[0];
    ull res=0; ll ans=0;
    rep(i,1,n) {
        if(!s.empty()&&s.top()==t[i])
            res-=s.top()*p[s.size()],s.pop();
        else
            s.push(t[i]),res+=s.top()*p[s.size()];
        ans+=cnt[res];
        ++cnt[res];
    }
    printf("%lld\n",ans);
    return 0;
}