luogu p4248 差异

题意： 求
\[ \sum_{i = 1}^n{\sum_{j = i + 1}^n}{Len(suf(i))+ Len(suf(j)) - 2\times LCP(suf(i),suf(j))},n\leq10^5 \]

sol：
前边那个玩意转化成\(n\times (n-1)\times (n+1)/2\)

后面那个减的东西显然是每个子区间\(Height\)最小值的和

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N = 5e5+7;typedef long long ll;
int x[N], y[N], sa[N], c[N*2], m, n; int rk[N*2], height[N*2];
char ss[N];
inline void getSA() {
  for (int i = 1; i <= n; i++) c[x[i] = ss[i]]++;
  for (int i = 2; i <= m; i++) c[i] += c[i - 1];
  for (int i = 1; i <= n; i++) sa[c[x[i]]--] = i;
  for (int siz = 1, p = 0; siz <= n; siz <<= 1, p = 0) { 
    for (int i = n - siz + 1; i <= n; i++) y[++p] = i;
    for (int i = 1; i <= n; i++) if (sa[i] > siz) y[++p] = sa[i] - siz;
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[x[y[i]]]++;
    for (int i = 2; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
    std :: swap(x, y), x[sa[1]] = 1, p = 1;
    for (int i = 2; i <= n; i++) x[sa[i]] = 
      (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + siz] == y[sa[i - 1] + siz]) ? p : ++p;
    if (p == n) break; m = p;
  } int k = 0;
  for (int i = 1; i <= n; i++) rk[sa[i]] = i;
  for (int i = 1; i <= n; i++) {
    if (rk[i] == 1) continue; 
    if (k) k--;
    int j = sa[rk[i] - 1];
    while (j + k <= n && i + k <= n && ss[i + k] == ss[j + k]) k++;
    height[rk[i]] = k;
  }
}
int stack[N*2], top = 0;int L[N], R[N];
int main() {
  scanf("%s", ss + 1), n = strlen(ss + 1); m = 255;getSA(); 
  ll ANS = (ll)((ll)n * (ll)(n + 1) * (ll)(n - 1)) / 2; stack[++top] = 1;
  for (int i = 2; i <= n; i++) {
    while (top && height[stack[top]] > height[i]) R[stack[top--]] = i;
    L[i] = stack[top], stack[++top] = i;
  } while (top) R[stack[top--]] = n + 1;
  for (int i = 1; i <= n; i++) 
    ANS -= 2ll * (ll)(R[i] - i) * (ll)(i - L[i]) * (ll)height[i];
  printf ("%lld", ANS);
return 0;
} 

luogu p4248 差异

原文：https://www.cnblogs.com/cjc030205/p/11638092.html