hdu 4622 Reincarnation

题意：还是比较容易理解，给出一个字符串，最长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 ++ ) ;

    }

    int solve ( int n )

    {

        int ans = 0 , i ;

        for ( i = 1 ; i <= n ; i ++ )

            ans += n - sa[i] - hei[i] ;

        return ans ;

    }

} 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

*/