CF653F Paper task 题解

题目链接：Paper task

题意：

给定一个长度为 \(n\) 的括号串，问有多少种本质不同的合法括号子串。

输入：长度 \(n\) 和字符串 \(S\) ，\(S\) 仅包含 ( 和 ) 。输出：答案。数据范围：\(1\le n\leq 5\times 10^5\) 。

考虑怎么算合法子串。把 ( 和 ) 分别看作 \(1\) 和 \(-1\) ，记 \(d_i\) 为他们的前缀和。

那么一个任意字符串 \(S\) 是合法的当且仅当 \(\forall i(1 < i \le |S|) ,~d_i \ge d_1 - 1\) 且 \(d_{|S|} = d_1 - 1,~d_1 = 1\) 。

对于固定的 \(i\) ，考虑二分合法的长度，用 ST 表维护区间 min ，这样可以找到最远的 \(r\) 使得 \(S[i..r]\) 合法

现在需要统计 \([i,r]\) 里有多少个点的 \(d\) 刚好等于 \(d_i-1\) ，这个可以用 vector 维护每个值的位置二分得到。

那么如何求出本质不同的子串呢？思路有点类似于这道题 P2408 不同子串个数。

即对于排名为 \(i\) 的后缀，它多统计的子串个数至多为 \(\operatorname{LCP}(i,i-1)\) ，也就是 \(\operatorname{height} i\)

记每个位置 \(i\) 我们二分到的是 \(r_i\) ，那么多统计的就是区间 \[ \left[\operatorname{sa}(i),~\min\{\operatorname{sa}(i) +\operatorname{height}(i)-1,\, r_{\operatorname{sa}(i)}\} \right] \] 中的合法串的个数。减去即可。注意 \(S_i= \mathtt{)}\) 的情况

~~至于为什么说和 P2408 有点像，是因为这样统计是不重不漏的，然后证明比较类似而已~~。

证明：因为所有后缀按字典序排序，故不存在前缀 \(S\) 不为 \(\mathrm{LCP}(i-1,i)\) 却为 \(\mathrm{LCP}(i-k,i)\) ，其中 \(k > 1\) 。

然后我们每次都减去了 \(i\) 相对于 \(i-1\) 多统计的部分（或者说统计正确了），于是这么统计是不重不漏的。\(\square\)

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void down(ll &x, ll y) { x > y ? x = y : 0; }
#define chk(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])
#define N ((int)(5e5 + 15))
const int _ = 5e5 + 10;

vector<int> vec[N * 2];
char s[N]; ll ans, d[N], st[20][N];
int n, ri[N], lg[N], sa[N], rk[N * 2], tmp[N * 2], height[N], cnt[N];
void sort(const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getheight()
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
void getsa()
{
    const int m = max(n, 666);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(m, w); sort(m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(chk(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
void buildST()
{
    for(int i = 2; i <= n + 5; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; i++) st[0][i] = d[i];
    for(int i = 1; i <= lg[n]; i++)
    {
        ll *f = st[i], *g = st[i - 1];
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
            down(f[j] = g[j], g[j + (1 << (i - 1))]);
    }
}
int query(int l, int r)
{
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}
int solve(int l, int r, ll v)
{
    v += _;
    ll L = lower_bound(vec[v].begin(), vec[v].end(), l) - vec[v].begin();
    ll R = upper_bound(vec[v].begin(), vec[v].end(), r) - vec[v].begin() - 1;
    if(L > R || L == vec[v].size()) return 0; else return R - L + 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> (s + 1); getsa(); getheight();
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == '(') d[i] = d[i - 1] + 1;
        else { d[i] = d[i - 1] - 1, vec[d[i] + _].push_back(i); }
    }
    buildST();
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == ')') continue;
        int l = i, r = n;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(query(i, mid) >= d[i] - 1) l = mid; else r = mid - 1;
        }
        ri[i] = l;
        if(s[i] == '(') ans += solve(i, ri[i], d[i] - 1);
    }
    for(int i = 2; i <= n; i++)
    {
        if(s[sa[i]] == ')') break;
        int r = min(sa[i] + height[i] - 1, ri[sa[i]]);
        ans -= solve(sa[i], r, d[sa[i]] - 1);
    }
    cout << ans << '\n';
    return 0;
}