題意：
給出一個的串 s，將 s 所有子串按照字典序排列好相接起來形成一個新串q次詢問，每一次詢問問新串中的第 k 個字符是什么，強制在線。

$|s|,q \le 2*10^{5} $

?

?

跟所有子串有關，那肯定要么是后綴自動機，要么是后綴樹。

考慮后綴自動機。即使后綴自動機單次詢問可以做到線性，在這題也無施展之地。鑒于他DAWG的性質，沒有什么東西可以維護。

然而后綴樹就不一樣了，[TJOI2015] 弦論有一種O(n+logn)的做法，可以參考Mangoyang的博客。

實際上考慮 parent 可以進一步優化算法的復雜度，考慮原先的 parent 樹一個節點代表的多個串都是最長的串的一個后綴，是一棵類似于前綴樹的結構，這樣不能適用于一些字典序上優美的性質。不妨將串反序插入到sam 中，這樣每一個點能代表的多個串都是最長的串的前綴，這些串從長到短在字典序上一定是有序的。擴展到整棵樹上，根據 minlen(u)=len(fa(u))+1 ，每個點代表的字符串都比其祖先代表的字符串的字典序大。于是可以計算出每一棵子樹代表了多少串，在 dfn 序上二分答案即可

類似的，也可以計算出后綴樹每一顆子樹代表的串的總長，并且通過構造可以使后綴樹上字符串的字典序與 dfn 序同時有序。這樣找到了后綴樹上的一個節點后，考慮一個子串其所代表的串長度在 [len(fa(u))+1,len(u)] 上連續，在這個節點上繼續二分答案就可以找到第k個字符所在的子串及它的長度，再計算一下就能知道第k個字符在s中的位置了。時間復雜度O(n+qlogn)

?

?

?

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 int const N=200000+10; 5 struct node{ 6 int len,fa,ch[26]; 7 }a[N<<1]; 8 int tot,ls,w[N<<1],num[N],sa[N<<1],cnt,pos[N<<1],son[N<<1][26]; 9 ll sum[N<<1],l[N<<1],sz[N<<1],qs[N<<1]; 10 char s[N]; 11 void add(int c,int id){ 12 int p=ls; 13 int np=ls=++tot; 14 a[np].len=a[p].len+1; 15 w[tot]=id; 16 sz[tot]=1; 17 for(;p&&!a[p].ch[c];p=a[p].fa) a[p].ch[c]=np; 18 if(!p) a[np].fa=1; 19 else { 20 int q=a[p].ch[c]; 21 if(a[q].len==a[p].len+1) a[np].fa=q; 22 else { 23 int nq=++tot; 24 a[nq]=a[q]; 25 a[nq].len=a[p].len+1; 26 a[q].fa=a[np].fa=nq; 27 for(;p&&a[p].ch[c]==q;p=a[p].fa) 28 a[p].ch[c]=nq; 29 } 30 } 31 } 32 void dfs(int x){ 33 if(!x ) return ; 34 pos[++cnt]=x; 35 for(int i=0;i<26;i++) 36 dfs(son[x][i]); 37 } 38 int main(){ 39 scanf("%s",s); 40 int len=strlen(s); 41 tot=ls=1; 42 for(int i=len-1;i>=0;i--) 43 add(s[i]-'a',i+1); 44 for(int i=2;i<=tot;i++) 45 sum[i]=1; 46 for(int i=1;i<=tot;i++) num[a[i].len]++; 47 for(int i=1;i<=len;i++) num[i]+=num[i-1]; 48 for(int i=1;i<=tot;i++) sa[num[a[i].len]--]=i; 49 for(int i=tot;i>=1;i--){ 50 int x=sa[i]; 51 int f=a[x].fa; 52 sz[f]+=sz[x]; 53 w[f]=w[f ]? w[f]:w[x]; 54 } 55 for(int i=2;i<=tot;i++){ 56 int x=a[i].fa; 57 int y=s[w[i]+a[a[i].fa].len-1]-'a'; 58 son[x][y]=i; 59 } 60 dfs(1); 61 for(int i=2;i<=tot;i++) { 62 int t=pos[i]; 63 ll x=a[a[t].fa].len+1; 64 ll y=a[t].len; 65 ll tmp=sz[t]*(x+y)*(y-x+1)/2; 66 qs[i]=qs[i-1]+tmp; 67 } 68 69 int q; 70 scanf("%d",&q); 71 ll g=0; 72 while (q--){ 73 ll p,m; 74 scanf("%lld%lld",&p,&m); 75 ll k=p*g % m +1; 76 int t=lower_bound(qs+1,qs+tot+1,k)-qs; 77 k-=qs[t-1]; 78 t=pos[t]; 79 ll x=a[a[t].fa].len+1; 80 ll y=a[t].len; 81 ll tmp=sz[t]*(x+y)*(y-x+1)/2; 82 ll l=x,r=y; 83 while (l<r){ 84 ll mid=(l+r)/2; 85 tmp=sz[t]*(x+mid)*(mid-x+1)/2; 86 if(tmp>=k) r=mid; 87 else l=mid+1; 88 } 89 k-=sz[t]*(x+r-1)*(r-x)/2; 90 k=(k-1) % r+1; 91 int c=w[t]+k-2; 92 printf("%c\n",s[c]); 93 g+=s[c]; 94 } 95 return 0; 96 } View Code

?

轉載于:https://www.cnblogs.com/ZJXXCN/p/11054391.html

總結

以上是生活随笔為你收集整理的Codechef January Challenge 2018 - Killjee and k-th letter的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。