题意：很简单的，就是给一个字符串，然后给出n个区间，输出两个ans，一个是所有区间的长度和，另一个是区间i跟区间i-1的最长公共前缀的长度的数值的长度，加上不是公共部分的字符个数，加2，累加起来。
解题思路：后缀数组裸题。。用rmq求最长公共前缀，询问就是o（1）的。有队伍用暴力的方法过的，对于i区间与i-1区间，如果左端点一样，就去长度小的那个，否则就暴力枚举相同的前缀。但我认为这样是不可以的，比如我的数据是10w个a，询问10w，第i个区间的左端点是i，所有右端点是len[s]，那这样的复杂度应该是o(n^2)吧。所以还是后缀数组靠谱。。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll __int64
using namespace std ;
const int maxn = 511111 ;
int p[maxn] ;
int min ( int a , int b ) { return a < b ? a : b ; }
int dp[25][maxn] , f[maxn] , fuck , n , l[maxn] , r[maxn] ;
ll ans1 , ans2 , d[maxn] ;
ll get ( int n ) {
ll i = 0 ;
if ( n == 0 ) i = 1 ;
while ( n ) {
i ++ ;
n /= 10 ;
}
return i + 1 ;
}
struct Suf{
int wa[maxn] , wb[maxn] , ws[maxn] , wv[maxn] ;
int rank[maxn] , hei[maxn] , sa[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 , k , 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 ,x[sa[0]] = 0 , p = 1 , i = 1 ; i < n ; i ++ )
x[sa[i]] = cmp ( y , sa[i-1] , sa[i] , j ) ? p - 1 : p ++ ;
}
k = 0 ;
for ( i = 1 ; i < n ; i ++ ) rank[sa[i]] = i ;
for ( i = 0 ; i < n - 1 ; hei[rank[i++]] = k )
for ( k ? k -- : 0 , j = sa[rank[i]-1] ; r[i+k] == r[j+k] ; k ++ ) ;
}
void rmq ( int n ) {
int i , j ;
for ( i = 1 ; i <= n ; i ++ ) dp[0][i] = hei[i] ;
for ( i = 1 ; i <= 20 ; i ++ )
for ( j = 1 ; j + ( 1 << i ) - 1 <= n ; j ++ )
dp[i][j] = min ( dp[i-1][j] , dp[i-1][j+(1<<(i-1))] ) ;
}
int query ( int l , int r ) {
if ( l > r ) swap ( l , r ) ;
l ++ ;//要从height[l+1]到height[r]之间求最小值
if ( l == r ) return dp[0][l] ;
int k = r - l + 1 ;
return min ( dp[f[k]][l] , dp[f[k]][r-(1<<f[k])+1] ) ;
}
void solve () {
int i , j , k ;
for ( i = 2 ; i <= n ; i ++ ) {
ll add ;
if ( l[i] == l[i-1] ) add = min ( d[i] , d[i-1] ) ;
else add = query ( rank[l[i-1]] , rank[l[i]] ) ;
// printf ( "add = %I64d , d1 = %I64d , d2 = %I64d
" , add , d[i-1] , d[i] ) ;
add = min ( add , min ( d[i] , d[i-1] ) ) ;
ans2 += get ( add ) ;
// printf ( "add = %I64d
" , d[i] - add + 1 ) ;
ans2 += (ll) d[i] - add + 1 ;
// printf ( "ans2 = %I64d
" , ans2 ) ;
}
}
} arr ;
char s1[maxn] ;
int s[maxn] ;
int main () {
int cas , i , j , ca = 0 ;
j = 0 ;
for ( i = 1 ; i < maxn - 1111 ; i ++ ) {
if ( i > 1 << j + 1 ) j ++ ;
f[i] = j ;
}
while ( scanf ( "%s" , s1 ) != EOF ) {
ans1 = ans2 = 0 ;
int len = strlen ( s1 ) ;
scanf ( "%d" , &n ) ;
for ( i = 1 ; i <= n ; i ++ ) {
scanf ( "%d%d" , &l[i] , &r[i]) , r[i] -- , d[i] = r[i] - l[i] + 1 ;
ans1 += (ll) d[i] + 1 ;
}
for ( i = 0 ; i < len ; i ++ ) s[i] = s1[i] ;
s[len] = 0 ;
arr.da ( s , len + 1 , 555 ) ;
ans2 = 2 + d[1] + 1 ;
// printf ( "ans2 = %I64d
" , ans2 ) ;
arr.rmq ( len ) ;
arr.solve () ;
printf ( "%I64d %I64d
" , ans1 , ans2 ) ;
}
}