「Bzoj 3238」「AHOI2013」差异 (后缀数组+并查集/单调栈)

BZOJ 3238
题意:给定一个长度为 $n$ 的字符串 $S$,令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求
$$
\sum_{i=1}^n \sum_{j=1}^{i-1} \text{len}(T_i) + \text{len}(T_j) - 2 \times \text{lcp}(T_i, T_j)
$$
其中,$\text{len}(a)$ 表示字符串 $a$ 的长度,$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

先将前面的求出来,等于$\frac{n(n+1)(n-1)}{2}​$, (可以分析一下合式组成或者将$j​$提取出来)

可以用艾佛森括号证明。
$$
\begin{aligned}
ans &= \sum_{i=1}^n\sum_{j=1}^i i+j \
&= \sum_{i=1}^n\sum_{j=1}^n (i+j)[j > i] \
&= \sum_{i=1}^n\sum_{j=1}^n i[j > i] + \sum_{i=1}^n\sum_{j=1}^n j[j > i] \
&= \sum_{i=1}^ni(n-i) + \sum_{i=1}^n\sum_{j=1}^n i(i-1) \
&= \sum_{i=1}^ni(n-i) + i(i-1) \
&= (n-1)\sum_{i=1}^ni \
&= (n-1)\frac{n(n+1)(n-1)}{2} \
\end{aligned}
$$

考虑后面的$\text{lcp}(a,b)$,就是任意两个串的$\text{lcp}$的值。
求出后缀数组,则$[2,n]$上$height$的每个区间对答案贡献区间最小值。

而这里可以仿造Bzoj 4199,用并查集来做
下面考虑求每个区间最小值和的方法,这个是一个经典做法,即用单调栈解。
我们对于每个$i \in [2,n]$,求出$L_i, R_i$分别表示这个$i$位置能扩展到左右多少位置(即当前$i$的$height$值的扩展区域)
那么最后答案就是$\sum\limits_{i=2}^n (i - L_i)(R_i - i) $,即为区间端点在$i​$两端的方案。

考虑左边界怎么扩展,我们找到离$i$左边最近的$height_j \leq height_i$,则$L_i=j$
右边界即找到离$i$右边最近的$height_j \geq height_i$,则$R_i=j$

那么求单调栈维护这个就行了,单调栈维护的标志有上面加粗的关键字。具体可以看代码实现。注意处理一下边界状态。上面的可以画图更加清晰

知识点
1、求每个区间最小值和的方法:单调栈

单调栈:

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 5;

    char ch[MAXN];
    int a[MAXN], n, m;
    int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];

    void build() {//11?¨¬o¨®¡Áo¨ºy¡Á¨¦ 
        for (int i = 1; i <= m; ++i) tax[i] = 0;
        for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
        for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
        for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;//?¨´¨ºy??D¨°??¦Ì¨²¨°???

        for (int k = 1; k <= n; k <<= 1) {
            int p = 0;
            for (int i = n - k + 1; i <= n; i++) tp[++p] = i;//(n-k)~(n-1)?T¦Ì¨²?t1??¨¹¡Á?¡ê??¨´¨°???D¨°¨®|?????¨²?¡ã??
            for (int i = 1; i <= n; i++) if (SA[i] > k) tp[++p] = SA[i] - k;
            //??¨®DSA[i]>=k¦Ì?SA[i]2?¨º?¦Ì¨²?t1??¨¹¡Á?¦Ì????? 
            //¡ä¨®¨ª??D?¨¦¨°??¡ä3?¦Ì¨²¨°?1??¨¹¡Á?o¨ª¦Ì¨²?t1??¨¹¡Á?¦Ì??????¨¤2?k¡ê?1¨ºSA[i] - k 
            for (int i = 1; i <= m; ++i) tax[i] = 0;
            for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;//x[tp[i]]?¨¤¦Ì¨¨¨®¨²????¦Ì¨²i¦Ì?¦Ì¨²?t1??¨¹¡Á?¦Ì?¦Ì¨²¨°?1??¨¹¡Á?¦Ì????? 
            for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
            for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];//¡À¡ê?¡è¨¢?¦Ì¨²¨°?1??¨¹¡Á?¦Ì??3D¨°?¨´??¦Ì¨²?t1??¨¹¡Á? 
            //?¨´¨ºy??D¨°¦Ì¨²¨°?1??¨¹¡Á?(rank[i]¦Ì?¨ºy?¦Ì)o¨ª¦Ì¨²?t1??¨¹¡Á?(tp[i]¦Ì???¡À¨º) 
            swap(rk, tp);//¡ä?¨º¡Àtp??¨®?¡ê??Y¡ä?¨¦?¨°???rank¦Ì??¦Ì
            p = 1, rk[SA[1]] = 1;
            for (int i = 2; i <= n; ++i) 
                rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
            //??????¦Ì¨²i¦Ì?¨ºy¦Ì?rank¡ê?¡ã¡äsa?3D¨°?¨¹1?¡À¡ê?¡èrank¦Ì??y¨¨¡¤D?¡ê?¦Ì?¨º?¨°acmp?D??¨®?¨¦?¨°???¡Á?¡¤?¡ä??¨¤¦Ì¨¨¦Ì??¨¦?? 
            if (p >= n) break;//???|¡ê?¨°??-??¨®D???¡ä?a?? 
            m = p; 
        }
        int k = 0;//k¨º?¡À¨¨i-1?¡ã¨°???¦Ì?o¨®¡Áo
        for (int i = 1; i <= n; ++i) {//H[0], H[1], H[2] ...¦Ì??3D¨°???? 
            if (k) k--;//¡ä¨®k-1?a¨º?¡À¨¨?? ,??¨®??¨¢??H[i]>=H[i-1]-1, ¡Á?3¡è1?12?¡ã¡Áo¦Ì?3¡è?¨¨?¨¢¨¦¨´¨º?k-1(k = H[i-1])
            int j = SA[rk[i] - 1]; //?¡ã¨°???¦Ì?o¨®¡Áo???? 
            while (ch[i + k] == ch[j + k]) k++; //¨ª¨´o¨®¡À¨¨?? 
            height[rk[i]] = k;  //?¨¹D?¡äe¡ã? 
        }
    }

    LL L[MAXN], R[MAXN], st[MAXN], top = 0, ans = 0;

    void clean() {
        m = 30;
    }
    int solve() {

        clean();
        scanf("%s", ch + 1);
        n = strlen(ch + 1);
        for (int i = 1; i <= n; ++i) a[i] = ch[i] - 'a' + 1, ans += 3ll * i * (i - 1ll) / 2ll;
        build();

        st[top = 1] = 1;
        for (int i = 2; i <= n; ++i) {
            while (top && height[st[top]] > height[i]) R[st[top--]] = i; // 找到第一个 height[j] <= height[i], 并且没找到时 height[j] > height[i],则可以更新 j 的 R
            L[i] = st[top];
            st[++top] = i;
        }
        while (top) R[st[top--]] = n + 1;
        for (int i = 1; i <= n; ++i) 
            ans -= 1ll * (R[i] - i) * (i - L[i]) * height[i] * 2ll;

        printf("%lld\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
//22:37
/*
*/

并查集:

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 5;

    char ch[MAXN];
    int a[MAXN], n, m;
    int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];

    void build() {//¹¹Ôìºó׺Êý×é 
        for (int i = 1; i <= m; ++i) tax[i] = 0;
        for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
        for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
        for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;//»ùÊýÅÅÐòÅŵÚÒ»ÂÖ

        for (int k = 1; k <= n; k <<= 1) {
            int p = 0;
            for (int i = n - k + 1; i <= n; i++) tp[++p] = i;//(n-k)~(n-1)ÎÞµÚ¶þ¹Ø¼ü×Ö£¬ËùÒÔÅÅÐòÓ¦¸ÃÅÅÔÚÇ°Ãæ
            for (int i = 1; i <= n; i++) if (SA[i] > k) tp[++p] = SA[i] - k;
            //Ö»ÓÐSA[i]>=kµÄSA[i]²ÅÊǵڶþ¹Ø¼ü×ÖµÄλÖà 
            //´ÓͼÖпÉÒÔ¿´³öµÚÒ»¹Ø¼ü×ֺ͵ڶþ¹Ø¼ü×ÖµÄλÖÃÏà²îk£¬¹ÊSA[i] - k 
            for (int i = 1; i <= m; ++i) tax[i] = 0;
            for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;//x[tp[i]]ÏàµÈÓÚÅÅÃûµÚiµÄµÚ¶þ¹Ø¼ü×ֵĵÚÒ»¹Ø¼ü×ÖµÄÅÅÃû 
            for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
            for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];//±£Ö¤Á˵ÚÒ»¹Ø¼ü×ÖµÄ˳ÐòÔÙÅŵڶþ¹Ø¼ü×Ö 
            //»ùÊýÅÅÐòµÚÒ»¹Ø¼ü×Ö(rank[i]µÄÊýÖµ)ºÍµÚ¶þ¹Ø¼ü×Ö(tp[i]µÄϱê) 
            swap(rk, tp);//´ËʱtpûÓã¬ÔÝ´æÉÏÒ»ÂÖrankµÄÖµ
            p = 1, rk[SA[1]] = 1;
            for (int i = 2; i <= n; ++i) 
                rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
            //ËãÅÅÃûµÚiµÄÊýµÄrank£¬°´sa˳ÐòÄܹ»±£Ö¤rankµÄÕýÈ·ÐÔ£¬µ«ÊÇÒªcmpÅжÏÓëÉÏÒ»¸ö×Ö·û´®ÏàµÈµÄÇé¿ö 
            if (p >= n) break;//¼ôÖ¦£¬ÒѾ­Ã»ÓÐÖظ´ÔªËØ 
            m = p; 
        }
        int k = 0;//kÊDZÈi-1Ç°Ò»ÃûµÄºó׺
        for (int i = 1; i <= n; ++i) {//H[0], H[1], H[2] ...µÄ˳Ðò¼ÆËã 
            if (k) k--;//´Ók-1¿ªÊ¼±È½Ï ,ÔËÓýáÂÛH[i]>=H[i-1]-1, ×¹«¹²Ç°×ºµÄ³¤¶ÈÖÁÉÙÊÇk-1(k = H[i-1])
            int j = SA[rk[i] - 1]; //Ç°Ò»ÃûµÄºó׺λÖà 
            while (ch[i + k] == ch[j + k]) k++; //Íùºó±È½Ï 
            height[rk[i]] = k;  //¸üд𰸠
        }
    }

    LL ans = 0;
    vector<int > vec[MAXN];
    int sz[MAXN], f[MAXN];

    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
    void merge(int x, int y, int len) {
        if (sz[x] > sz[y]) swap(x, y);
        ans -= 2ll * sz[x] * sz[y] * len;
        f[x] = y, sz[y] += sz[x];
    }

    void clean() {
        m = 30;
    }
    int solve() {

        clean();
        scanf("%s", ch + 1);
        n = strlen(ch + 1);
        for (int i = 1; i <= n; ++i) a[i] = ch[i] - 'a' + 1, ans += 3ll * i * (i - 1ll) / 2ll;
        build();

        for (int i = 1; i <= n; ++i) vec[height[i]].push_back(i), sz[i] = 1, f[i] = i;

        for (int len = n - 1; len >= 1; --len) {
            for (int i = 0; i < (int)vec[len].size(); ++i) {
                int v = vec[len][i];
                merge(find(v), find(v - 1), len);
            }
        }

        printf("%lld\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
//22:37
/*
*/
------ 本文结束 ------