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$
那么求单调栈维护这个就行了，单调栈维护的标志有上面加粗的关键字。具体可以看代码实现。注意处理一下边界状态。上面的可以画图更加清晰
单调栈：
#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
/*
*/
