題意：還是比較容易理解，給出一個字符串，最長2000，q個詢問，每次詢問[l,r]區間內有多少個不同的字串。
（為了與論文解釋統一，這裡解題思路裡sa數組的值是從1到n，但其實代碼中我的sa數組的值是從0到n-1）。
解題思路：09年的後綴數組論文裡有一個類似的題，求一個字串的不同字串有多少個。問不同的字串有多少個，即問對於每一個後綴，它的所有前綴中，與其他後綴的前綴不同的有幾個。解法是按rank從大到小將後綴一個個加進來，那麼每加進一個後綴，將會增加n-sa[i]+1個前綴，但這些前綴中，有一些是之前出現過的，之前出現過的個數就是i與之前加進來的所有後綴的最長公共前綴的長度，很顯然，就是height[i]。那麼每次能獲得的不同的字串的個數就是n-sa[i]+1-height[i]。比賽時，嘗試的方法是將[l,r]構成一個新的字符串，直接進行一遍 da 的處理，但是超時了（據說有人過了，不可思議）。賽後進行改進，先對整個字符串進行一遍 da 處理（後綴數組基本處理），將rank，sa，height數組都處理出來。q個詢問，一次次回答，剛開始我想到的是對[l,r]構成的後綴根據他們的rank進行排序，然後根據rank值進行類似論文問題的方法處理，後來也還是超時。但其實我們根本不用排序，因為我們之前已經處理除了rank數組和sa數組。我們用一個pos數組進行記錄l到r區間出現的後綴，賦初值為-1，pos[i]表示排名第i的後綴是誰，與sa的意義相同，但這裡我們只要l到r之間的後綴，所以對其他賦值為-1。然後按名次從1到n掃描下來，如果pos[i] == -1那麼表示該名次下的後綴並不在[l,r]區間中，那麼不做處理。否則就做類似論文題的方法進行處理。但這裡要注意一個問題，對於加進來的一個在[l,r]後綴i，我們能獲得的新的不同的前綴（即要獲得的子串）個數為n-sa[i]+1-d，其中d並不是上面的height[i]了，因為對於height[i]，有可能它的長度已經超過r-sa[i]+1(這是對於i後綴，能提供的最長長度)。所以d應該是對於i之前所有的加進來的後綴j，取max( min(lcp(j,i),min(r-j+1,r-i+1)) )。當然我們不能每次都枚舉j，但我們只要每次都更新下這個d就好了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include <stdlib.h>
#define ll __int64
using namespace std ;
const int maxn = 1111111 ;
ll f[maxn] , g[maxn] ;
int wa[maxn] , wb[maxn] , wv[maxn] , ws[maxn] , pos[maxn] ;
struct suf
{
int sa[maxn] , hei[maxn] , rank[maxn] ;
int cmp ( int *r , int i , int j , int l )
{
return r[i] == r[j] && r[i+l] == r[j+l] ;
}
void da ( int *r , int n , int m )
{
int *x = wa , *y = wb , *t ;
int i , j , p ;
for ( i = 0 ; i < m ; i ++ ) ws[i] = 0 ;
for ( i = 0 ; i < n ; i ++ ) ws[x[i]=r[i]] ++ ;
for ( i = 1 ; i < m ; i ++ ) ws[i] += ws[i-1] ;
for ( i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[i]]] = i ;
for ( j = 1 , p = 1 ; p < n ; j *= 2 , m = p )
{
for ( p = 0 , i = n - j ; i < n ; i ++ ) y[p++] = i ;
for ( i = 0 ; i < n ; i ++ ) if ( sa[i] >= j ) y[p++] = sa[i] - j ;
for ( i = 0 ; i < m ; i ++ ) ws[i] = 0 ;
for ( i = 0 ; i < n ; i ++ ) ws[x[i]] ++ ;
for ( i = 1 ; i < m ; i ++ ) ws[i] += ws[i-1] ;
for ( i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[y[i]]]] = y[i] ;
for ( t = x , x = y , y = t , p = 1 , x[sa[0]] = 0 , i = 1 ; i < n ; i ++ )
x[sa[i]] = cmp ( y , sa[i-1] , sa[i] , j ) ? p - 1 : p ++ ;
}
int k = 0 ;
for ( i = 1 ; i < n ; i ++ ) rank[sa[i]] = i ;//這裡sa[0]不用加進去了
for ( i = 0 ; i < n - 1 ; hei[rank[i++]] = k )//同上，rank[n-1]=0
for ( k ? k -- : 0 , j = sa[rank[i]-1] ; r[i+k] == r[j+k] ; k ++ ) ;
}
} arr ;
int s1[maxn] , dp[20][2222] ;
void rmq ( int n )
{
int i , j ;
f[0] = 1 ;
for ( i = 1 ; i <= 15 ; i ++ )
f[i] = f[i-1] * 2 ;
g[0] = -1 ;
for ( i = 1 ; i < 2222 ; i ++ )
g[i] = g[i>>1] + 1 ;
for ( i = 1 ; f[i] <= n ; i ++ )
for ( j = 1 ; j + f[i] - 1 <= n ; j ++ )
dp[i][j] = min ( dp[i-1][j] , dp[i-1][j+f[i-1]] ) ;
}
int query ( int l , int r )
{
if ( l == r ) return dp[0][l] ;
if ( l > r ) swap ( l , r ) ;
int i , j , k ;
k = g[r-l+1] ;
return min ( dp[k][l] , dp[k][r-f[k]+1] ) ;
}
char s[maxn] ;
int num[maxn] ;
int main ()
{
int n , k , i , l , r ;
int cas ;
scanf ( "%d" , &cas ) ;
while ( cas -- )
{
int q ;
scanf ( "%s" , s ) ;
int len = strlen ( s ) ;
for ( i = 0 ; i < len ; i ++ ) s1[i] = s[i] ;
s1[len] = 0 ;
arr.da ( s1 , len + 1 , 555 ) ;
for ( i = 1 ; i <= len ; i ++ )
dp[0][i] = arr.hei[i] ;
rmq ( len ) ;
n = len ;
scanf ( "%d" , &q ) ;
while ( q -- )
{
scanf ( "%d%d" , &l , &r ) ;
int ans = ( r - l + 1 ) * ( r - l + 2) / 2 ;
for ( i = 0 ; i <= n ; i ++ ) pos[i] = -1 ;
for ( i = l ; i <= r ; i ++ )
pos[arr.rank[i-1]] = i - 1 ;
int last = -1 , d = 0 ;
for ( i = 1 ; i <= n ; i ++ )
{
if ( pos[i] != -1 )
{
if ( last != -1 )
{
int t = query ( arr.rank[last] + 1 , arr.rank[pos[i]] ) ;
d = min ( d , t ) ;
d = max ( d , min ( t , r - last ) ) ;
ans -= min ( d , r - pos[i] );
}
last = pos[i] ;
}
}
printf ( "%d\n" , ans ) ;
}
}
}
/*
100
baaba
100
3 4
100
hgtll
100
1 3
100
jghgtuklllsdd
100
3 5
*/
