题解 P1117 【[NOI2016]优秀的拆分】

· · 题解

提供一个使用 runs 的做法，时间复杂度 O(n\log n)。

这个做法完全不需要 SA 预处理 LCP，用到的最高妙的算法就是二分哈希，但是时间复杂度依然是优秀的一个 \log。lg 上用时最慢的点用了 40ms，其它都是 2~3ms，看上去做一次询问 1e6 根本不成问题。

前置知识：Lyndon 分解

Lyndon 分解网上资料很多，这部分不在赘述，只补充一部分定义。

考虑如何求出一个串的所有 run。

我们把串 Lyndon 分解，然后枚举一个 i，设 ed[i] 是这一段 Lyndon 分解的边界，那么以 i 开头的 Lyndon 子串的右端点不会超过 ed[i]，一段 Lyndon Root 也必然是 s[i:ed[i]] 的子串。

我们可以二分哈希找到包含 s[i:ed[i]] 的极长循环子串 s[l:r]，如果这段子串合法（满足 runs 的定义），那么就找到了一个 run。显然一个 s[l:r] 可能被统计多次，我们应当取周期最小的那一次。

如果对 \iota=0/1 均做一遍这样的操作，就可以得到所有的 run。

然后考虑计算“以某个位置结尾的平方串的数量”和“以某个位置开头的平方串的数量”，显然一个平方串会自然地对应一个 run 的子串。

The Runs Theorem 指出，一个串的 run 的数量不超过串长，那么我们接下来只要枚举一个 run，然后枚举最小周期的倍数 l。因为 run 满足它是极长的一段，那么在这一段里面每个长为 l 的子串肯定都是一个平方串，我们直接在这一段里面差分即可。

可以证明，这一部分的复杂度不超过 O(n\log n)。因此总复杂度 O(n\log n)，代码复杂度极低。

参考实现：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define LL long long
const int CN = 3e4 + 10;
const int P = 191011109;
const int B = 39; int pB[CN];
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int ha[CN];
int get(int l, int r) {return add(ha[r], P - (1ll * ha[l - 1] * pB[r - l + 1] % P));}
int T, n; char ch[CN]; 
int LCP(int l1, int r1, int l2, int r2){
    if(ch[l1] != ch[l2]) return 0;
    int l = 1, r = min(r1 - l1 + 1, r2 - l2 + 1);
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(get(l1, l1 + mid - 1) == get(l2, l2 + mid - 1)) l = mid;
        else r = mid - 1;
    }
    return l;
}
int LCS(int l1, int r1, int l2, int r2){
    if(ch[r1] != ch[r2]) return 0;
    int l = 1, r = min(r1 - l1 + 1, r2 - l2 + 1);
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(get(r1 - mid + 1, r1) == get(r2 - mid + 1, r2)) l = mid;
        else r = mid - 1;
    }
    return l;
}
bool le(int l1, int r1, int l2, int r2){
    if(l1 == l2) return r1 < r2;
    int l = LCP(l1, r1, l2, r2);
    if(l1 + l > r1 || l2 + l > r2) return r1 - l1 < r2 - l2;
    return ch[l1 + l] < ch[l2 + l];
}
class PAIR{
  public: int l, r, p;
    bool operator < (const PAIR &o) const{
        return l ^ o.l ? l < o.l : (r ^ o.r ? p < o.p : r < o.r);
    }
    bool operator == (const PAIR &o) const{
        return l == o.l && r == o.r;
    } 
} ;
PAIR mp(int a, int b, int c) {PAIR o; o.l = a, o.r = b, o.p = c; return o;}
vector<PAIR> runs; int stk[CN], ed[CN], top;
void lyndon(){
    top = 0;
    for(int i = n; i; i--){
        stk[++top] = i;
        while(top > 1 && le(i, stk[top], stk[top] + 1, stk[top - 1])) top--;
        ed[i] = stk[top];
    }
    for(int i = 1; i <= n; i++){
        int j = ed[i], lcs = LCS(1, i - 1, 1, j), lcp = LCP(i, n, j + 1, n), l, r;
        l = i - lcs, r = j + lcp;
        if((r - l + 1) / (j - i + 1) > 1) runs.pb(mp(l, r, j - i + 1));
    }
}
int f[CN], g[CN];
int main()
{
    // freopen("_in.in", "r", stdin);
    n = 3e4, pB[0] = 1;
    for(int i = 1; i <= n; i++) pB[i] = 1ll * pB[i - 1] * B % P;
    T = read();
    while(T--){
        scanf("%s", ch + 1), n = strlen(ch + 1);
        for(int i = 1; i <= n; i++) ha[i] = add(1ll * B * ha[i - 1] % P, ch[i] - 'a');
        runs.clear();
        lyndon();
        for(int i = 1; i <= n; i++) ch[i] = 'a' + 'z' - ch[i];
        lyndon();
        sort(runs.begin(), runs.end());
        int len = unique(runs.begin(), runs.end()) - runs.begin();
        for(int i = 0; i < len; i++){
            int l = runs[i].l, r = runs[i].r, p = runs[i].p;
            for(int L = p + p; L <= r - l + 1; L += p + p){
                g[l]++, g[r - L + 2]--;
                f[l + L - 1]++, f[r + 1]--;
            }
        }
        for(int i = 1; i <= n; i++) f[i] += f[i - 1], g[i] += g[i - 1];
        LL ans = 0;
        for(int i = 1; i < n; i++) ans += 1ll * f[i] * g[i + 1];
        printf("%lld\n", ans);
        for(int i = 0; i <= n + 1; i++) f[i] = g[i] = 0;
    }
    return 0;
}