字母(letter)_26u

字母(letter)

【题目描述】

给定一个字符串。取出的所有子串，并按字典序从小到大排序，然后将这些排完序的字符串首尾相接，记为字符串。有次询问，每次询问中的第个字符。

是被加密的，每次询问给出两个正整数，设为之前所有询问答案的ASCII码之和。初始时为。则该次询问的。

 

【输入格式】

输入第一行包含一个字符串，第二行包含一个正整数。

接下来行，每行两个正整数P,M。

 

【输出格式】

输出行，分别表示每个询问的答案。

 

【输入样例】

caaacacbbbababba

6

3 101

16 101

21 41

22 129

33 131

40 100

 

【输出样例】

a

a

a

b

c

a

 

【数据范围与约定】

对于100%的数据，，中仅包含小写字母。

 

这是一道后缀树的题目

因为后缀树的先序遍历是可以按顺序找出所有的子串的

所以后缀自动机反着跑，建后缀树，具体方式参见dalao博客

然后就可以考虑一个点的father和它的关系

father的right集合比当前点是要多的，而且right集合的代表的长度是一段连续的区间

所以考虑一个点的贡献，那么就是一段连续长度的子串

对于每个节点有一个pos记录它的最后一个点在哪里，以及length长度

而且一个点的父亲的所有节点的开头必定不会是同一个字符，否则就会合并到父亲

那么一个点的长度就在length[fa[x]]+1到length[x]之间,然后在二分这里面的长度

得到一个length后，用pos找出具体是哪个字符就可以了

代码自己不想写，而且很不熟练，借的是yyyuuu dalao的代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ; 
#define LL long long 
int fa[400005] , to[400005][26] , mx[400005] , cnt[400005] , pos[400005] , linker[400005][26] , lzw , las ;
char s1[200005] , s2[200005] ; 
void insert ( int x , int id )  
{
	int np = ++lzw , nd = las ; las = lzw ; mx[np] = mx[nd] + 1 ; cnt[np] = 1 ; pos[np] = id ; 
	while ( nd != -1 && !to[nd][x] ) to[nd][x] = np , nd = fa[nd] ; 
	if ( nd == -1 ) { fa[np] = 0 ; return ; }
	int q = to[nd][x] ; 
	if ( mx[q] == mx[nd] + 1 ) { fa[np] = q ; return ; }
	int nq = ++lzw ; 
	fa[nq] = fa[q] , mx[nq] = mx[nd] + 1 ; for ( int i = 0 ; i < 26 ; i++ ) to[nq][i] = to[q][i] ; 
	fa[q] = fa[np] = nq ; pos[nq] = pos[q] ; 
	while ( nd != -1 && to[nd][x] == q ) to[nd][x] = nq , nd = fa[nd] ; 
} 
bool cmp ( const int &a , const int &b ) { return mx[a] < mx[b] ; }
LL s[400005] ; int hf , que[400005] ;  
void dfs ( int u ) 
{
	if ( u ) s[++hf] = 1ll * ( mx[u] + mx[fa[u]] + 1 ) * ( mx[u] - mx[fa[u]] ) / 2 * cnt[u] , que[hf] = u ; 
	for ( int i = 0 ; i < 26 ; i++ ) 
	    if ( linker[u][i] ) dfs ( linker[u][i] ) ;  
}   
void init ( ) 
{
	dfs ( 0 ) ; 
	for ( int i = 1 ; i <= hf ; i++ ) s[i] += s[i-1] ; 
}
LL K ; int Q ; 
char query ( ) 
{
	int l = 0 , r = lzw , pps ; 
	while ( l <= r ) 
	{
		int mid = l + r >> 1 ; 
		if ( s[mid] < K ) pps = mid , l = mid + 1 ; 
		else r = mid - 1 ; 
	} 
	K -= s[pps] ; int u = que[pps + 1] ; 
	l = mx[fa[u]] , r = mx[u] ; 
	while ( l <= r ) 
	{
		int mid = l + r >> 1 ;
		if ( 1ll * ( mid + mx[fa[u]] + 1 ) * ( mid - mx[fa[u]] ) / 2 * cnt[u] < K ) pps = mid , l = mid + 1 ; 
		else r = mid - 1 ; 
	}
	K -= 1ll * ( pps + mx[fa[u]] + 1 ) * ( pps - mx[fa[u]] ) / 2 * cnt[u] ;  
	K = ( K - 1 ) % ( pps + 1 ) + 1 ;
	return s2[pos[u] - K + 1] ;    
}
int main ( ) 
{
	fa[0] = -1 ; 
	scanf ( "%s" , s1 + 1 ) ; int havedinner = strlen ( s1 + 1 ) ; for ( int i = 1 ; i <= havedinner ; i++ ) s2[i] = s1[havedinner - i + 1] ;
	for ( int i = 1 ; i <= havedinner ; i++ ) insert ( s2[i] - 'a' , i ) ;  
	for ( int i = 1 ; i <= lzw ; i++ ) que[i] = i ; 
	sort ( que + 1 , que + lzw + 1 , cmp ) ; 
	for ( int i = lzw ; i >= 1 ; i-- ) cnt[fa[que[i]]] += cnt[que[i]] ;
	for ( int i = 1 ; i <= lzw ; i++ ) linker[fa[i]][s2[pos[i] - mx[fa[i]]] - 'a'] = i ; 
	init ( ) ; 	
	scanf ( "%d" , &Q ) ; 
	int tota = 0 ;
	while ( Q-- ) 
	{
		int p ; LL m ;
		scanf ( "%d%lld" , &p , &m ) ; 
		K = 1ll * p * tota % m ; K++ ; 
		char g = query ( ) ; 
		tota += g ; 
		printf ( "%c\n" , g ) ; 
	}
}