Killjee is trying to unlock a treasure. The key to the treasure is encrypted using a string S and Q queries. In each query, you need to find the K-th letter of a hidden string which is formed from the string S.
To form the hidden string, you should sort all substrings of S in lexicographical order and concatenate them. For example, if S = "abc", the hidden string would be "aababcbbcc". (See the sample explanation for details.)
In each query, the value of K is encoded in the following way:
For each query, print a single line containing one character — the K-th letter of the hidden string.
Subtask #1 (5 points): 1 ≤ |S| ≤ 50
Subtask #2 (15 points):
Subtask #3 (20 points): 1 ≤ Q ≤ 10
Subtask #4 (60 points): original constraints
Input: abc 3 1 1 2 3 5 6 Output: a b a
The substrings of S are "a", "b", "c", "ab", "abc", "bc". The lexicographical order of these strings is "a", "ab", "abc", "b", "bc", "c", so the hidden string is "a"+"ab"+"abc"+"b"+"bc"+"c" = "aababcbbcc".
For query 1, G = 0, so K = ( P · G ) % M + 1 = ( 1 · 0 ) % 1 + 1 = 1. The 1-st character of the hidden string is ‘a‘. We add the ASCII value of ‘a‘ (97) to G.
For query 2, G = 97, so K = ( 2 · 97 ) % 3 + 1 = 3. The 3-rd character of the hidden string is ‘b‘. We add the ASCII value of ‘b‘ (98) to G.
For query 3, G = 195, so K = ( 5 · 195 ) % 6 + 1 = 4. The 4-th character of the hidden string is ‘a‘. We add the ASCII value of ‘a‘ (97) to G.
给定一个字符串S。取出S的所有子串，并按字典序从小到大排序，然后将这些排完序的字符串首尾相接，记为字符串T。有Q次询问，每次询问T中的第K个字符。
K是被加密的，每次询问给出两个正整数P, M，设G为之前所有询问答案的 ASCII 码之和。初始时G为0。则该次询问的K = (P ? G) mod M。
跟所有子串有关，那肯定要么是后缀自动机，要么是后缀树。
考虑后缀自动机。即使后缀自动机单次询问可以做到线性，在这题也无施展之地。鉴于他DAWG的性质，没有什么东西可以维护。
然而后缀树就不一样了，[TJOI2015] 弦论有一种\(O(n+\log n)\)的做法，可以参考Mangoyang的博客。
实际上考虑 parent 可以进一步优化算法的复杂度，考虑原先的 parent 树一个节点代表的多个串都是最长的串的一个后缀，是一棵类似于前缀树的结构，这样不能适用于一些字典序上优美的性质。不妨将串反序插入到sam 中，这样每一个点能代表的多个串都是最长的串的前缀，这些串从长到短在字典序上一定是有序的。扩展到整棵树上，根据 \(minlen(u)=len(fa(u))+1\) ，每个点代表的字符串都比其祖先代表的字符串的字典序大。于是可以计算出每一棵子树代表了多少串，在 dfn 序上二分答案即可
类似的，也可以计算出后缀树每一颗子树代表的串的总长，并且通过构造可以使后缀树上字符串的字典序与 dfn 序同时有序。这样找到了后缀树上的一个节点后，考虑一个子串其所代表的串长度在 \([len(fa(u))+1,len(u)]\) 上连续，在这个节点上继续二分答案就可以找到第k个字符所在的子串及它的长度，再计算一下就能知道第k个字符在s中的位置了。时间复杂度\(O(n+q\log n)\)
后缀自动机本身之所以不能做这些事情，是因为没有很好的性质维护字典序。如果用dfs把所有路径按字典序找出来然后标号，节点重用很少，个数期望就是\(O(n^2)\)个。
十年OI一场空，不开long long见祖宗。
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int N=4e5+10;
char s[N];
int n,last=1,tot=1;
int ch[N][26],len[N],fa[N],pos[N],siz[N];
il void extend(int c,int po){
int p=last,cur=last=++tot;
len[cur]=len[p]+1,pos[cur]=po,siz[cur]=1;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur;
if(!p) fa[cur]=1;
else{
int q=ch[p][c];
if(len[q]==len[p]+1) fa[cur]=q;
else{
int clone=++tot;
copy(ch[q],ch[q]+26,ch[clone]);
len[clone]=len[p]+1,fa[clone]=fa[q],pos[clone]=pos[q];
fa[q]=fa[cur]=clone;
for(;ch[p][c]==q;p=fa[p]) ch[p][c]=clone;
}
}
}
int cnt[N],ord[N],e[N][26],ref[N],dfn;
ll sum[N];
void dfs(int u){
::ref[++dfn]=u;
sum[dfn]=(ll)siz[u]*(len[u]+len[fa[u]]+1)*(len[u]-len[fa[u]])/2;
for(int i=0;i<26;++i)if(e[u][i]) dfs(e[u][i]);
}
il int query(ll k){
int l=1,r=tot,mid;
while(l<r) sum[mid=l+r>>1]>=k?r=mid:l=mid+1;
k-=sum[l-1];
int x=::ref[l];
l=len[fa[x]]+1,r=len[x];
while(l<r){
mid=l+r>>1;
if((ll)siz[x]*(mid+len[fa[x]]+1)*(mid-len[fa[x]])/2>=k) r=mid;
else l=mid+1;
}
k-=(ll)siz[x]*(l+len[fa[x]])*(l-1-len[fa[x]])/2;
k=(k-1)%l+1;
return s[pos[x]+k-1];
}
int main(){
// freopen("letter.in","r",stdin),freopen("letter.out","w",stdout);
scanf("%s",s+1),n=strlen(s+1);
for(int i=n;i>=1;--i) extend(s[i]-'a',i);
for(int i=1;i<=tot;++i) ++cnt[len[i]];
for(int i=1;i<=n;++i) cnt[i]+=cnt[i-1];
for(int i=1;i<=tot;++i) ord[cnt[len[i]]--]=i;
for(int i=tot;i;--i) siz[fa[ord[i]]]+=siz[ord[i]];
for(int i=1;i<=tot;++i) e[fa[i]][s[pos[i]+len[fa[i]]]-'a']=i;
dfs(1),assert(dfn==tot);
for(int i=1;i<=dfn;++i) sum[i]+=sum[i-1];
ll G=0,P,M;
for(int Q=read<int>(),c;Q--;G+=c){
read(P),read(M);
printf("%c\n",c=query(P*G%M+1));
}
return 0;
}CodeChef KILLKTH Killjee and k-th letter
原文：https://www.cnblogs.com/autoint/p/10680332.html