problem

luogu-P4070

魔咒串由許多魔咒字符組成，魔咒字符可以用數字表示。例如可以將魔咒字符 $1,2$ 拼湊起來形成一個魔咒串 $[1,2]$。

一個魔咒串 S 的非空字串被稱為魔咒串 S 的生成魔咒。

例如 $S=[1,2,1]$ 時，它的生成魔咒有 $[1],[2],[1,2],[2,1],[1,2,1]$ 五種。

$S=[1,1,1]$ 時，它的生成魔咒有 $[1],[1,1],[1,1,1]$ 三種，最初 S 為空串。

共進行 $n$ 次操作，每次操作是在 $S$ 的結尾加入一個魔咒字符。每次操作后都需要求出，當前的魔咒串 $S$ 共有多少種生成魔咒。

solution

本質不同的子串個數，是后綴數組經典運用，$\sum n?i+1?h_i=\frac{n(n+1)}{2}?\sum h_i$。

考慮每次在字符串末尾加入一個數字的話，我們就需要每次重新求一遍所有的后綴，因為全都變了。$h$ 的變化也是動態不定的。

但如果反過來，每次在字符串開頭加入一個數字的話，相當于只是多加了一個后綴。$h$ 的變化是 $O(1)$ 的。

所以我們將 $n$ 個數組成的字符串反轉，提前求出每個后綴的排名，$h$ 數組，建立 $st$ 表。

倒著枚舉 $i=n～1$，加入 $i$ 開頭的后綴，然后查詢與其最相近的后綴，即 $rnk[i]$ 的前后綴。

重復的子串個數為 $cnt+lcp(pre,rnk[i])+lcp(rnk[i],nxt)?lcp(pre,nxt)$。

用 $set$ 維護 $rnk$ 數組即可，當然也可以鏈表等各種快速查前后綴的工具。

code

#include <bits/stdc++.h> using namespace std; #define maxn 100005 #define int long long int h[maxn], s[maxn], x[maxn], sa[maxn], id[maxn], tot[maxn], rnk[maxn << 1]; int lg[maxn], st[maxn][20]; set < int > NB; int n, m;void SA() {for( int i = 1;i <= n;i ++ ) tot[x[i] = s[i]] ++;for( int i = 1;i <= m;i ++ ) tot[i] += tot[i - 1];for( int i = n;i;i -- ) sa[tot[x[i]]--] = i;for( int k = 1;k <= n;k <<= 1 ) {int num = 0;for( int i = n - k + 1;i <= n;i ++ ) id[++ num] = i;for( int i = 1;i <= n;i ++ ) if( sa[i] > k ) id[++ num] = sa[i] - k;memset( tot, 0, sizeof( tot ) );for( int i = 1;i <= n;i ++ ) tot[x[i]] ++;for( int i = 1;i <= m;i ++ ) tot[i] += tot[i - 1];for( int i = n;i;i -- ) sa[tot[x[id[i]]]--] = id[i];for( int i = 1;i <= n;i ++ ) rnk[i] = x[i];x[sa[1]] = num = 1;for( int i = 2;i <= n;i ++ )x[sa[i]] = (rnk[sa[i]] == rnk[sa[i - 1]] and rnk[sa[i] + k] == rnk[sa[i - 1] + k]) ? num : ++ num;if( n == num ) break;m = num;} }void height() {for( int i = 1;i <= n;i ++ ) rnk[sa[i]] = i;for( int i = 1, k = 0;i <= n;i ++ ) {if( rnk[i] == 1 ) continue;if( k ) k --;int j = sa[rnk[i] - 1];while( i + k <= n and j + k <= n and s[i + k] == s[j + k] ) k ++;h[rnk[i]] = k;} }void ST() {lg[0] = -1; for( int i = 1;i <= n;i ++ ) lg[i] = lg[i >> 1] + 1;for( int i = 1;i <= n;i ++ ) st[i][0] = h[i];for( int j = 1;(1 << j) <= n;j ++ )for( int i = 1;i + (1 << j) - 1 <= n;i ++ )st[i][j] = min( st[i][j - 1], st[i + (1 << j - 1)][j - 1] ); }int lcp( int l, int r ) {l ++; int i = lg[r - l + 1];return min( st[l][i], st[r - (1 << i) + 1][i] ); }signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &s[i] ), x[i] = s[i];sort( x + 1, x + n + 1 );m = unique( x + 1, x + n + 1 ) - x - 1;for( int i = 1;i <= n;i ++ ) s[i] = lower_bound( x + 1, x + m + 1, s[i] ) - x;reverse( s + 1, s + n + 1 );SA();height();ST();NB.insert( 0 );NB.insert( n + 1 );int ans = 0;for( int i = n;i;i -- ) {NB.insert( rnk[i] );auto it = NB.find( rnk[i] );auto pre = it; -- pre;auto nxt = it; ++ nxt;ans = ans - lcp( *pre, *nxt ) + lcp( *pre, rnk[i] ) + lcp( rnk[i], *nxt );printf( "%lld\n", (n - i + 1) * (n - i + 2) / 2 - ans );}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[SDOI2016] 生成魔咒（后缀数组SA + st表 + set）动态不同子串个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。