[ccKILLKTH]Killjee and k-th letter

悠悠 2021-11-17 15:34 162阅读 0赞

建立后缀树（即反序插入字符串的parent树），然后可以发现按照dfs序排列满足其反串按字典序从小到大排列，那么就可以维护出每一刻子树的串长和，然后直接在dfs序上二分确定节点，再在节点内部乱搞即可求出答案。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 200005
     4 #define ll long long
     5 int V,last,ans,a[N<<1],sz[N<<1],mi[N<<1],id[N<<1],len[N<<1],fa[N<<1],ch[N<<1][31];
     6 ll k,mod,l[N<<1],sum[N<<1];
     7 char s[N];
     8 void add(int c){
     9     int p=last,np=last=++V;
    10     len[np]=len[p]+1;
    11     sz[np]=1;
    12     for(;(p)&&(!ch[p][c]);p=fa[p])ch[p][c]=V;
    13     if (!p)fa[np]=1;
    14     else{
    15         int q=ch[p][c];
    16         if (len[q]==len[p]+1)fa[np]=q;
    17         else{
    18             int nq=++V;
    19             len[nq]=len[p]+1;
    20             memcpy(ch[nq],ch[q],sizeof(ch[q]));
    21             fa[nq]=fa[q];
    22             fa[np]=fa[q]=nq;
    23             for(;(p)&&(ch[p][c]==q);p=fa[p])ch[p][c]=nq;
    24         }
    25     }
    26 }
    27 void dfs(int k){
    28     a[++a[0]]=k;
    29     for(int i=0;i<26;i++)
    30         if (ch[k][i])dfs(ch[k][i]);
    31 }
    32 int main(){
    33     int t;
    34     scanf("%s%d",s,&t);
    35     V=last=1;
    36     int n=strlen(s);
    37     for(int i=n-1;i>=0;i--)add(s[i]-'a');
    38     for(int i=1;i<=V;i++)a[len[i]]++;
    39     for(int i=1;i<=n;i++)a[i]+=a[i-1];
    40     for(int i=1;i<=V;i++)id[a[len[i]]--]=i;
    41     for(int i=1,j=n;i<=V;i++)
    42         if (sz[i])mi[i]=--j;
    43     memset(a,0,sizeof(a));
    44     for(int i=V;i;i--){
    45         sz[fa[id[i]]]+=sz[id[i]];
    46         mi[fa[id[i]]]=mi[id[i]];
    47     }
    48     for(int i=V;i;i--)l[i]=(len[fa[i]]+len[i]+1LL)*(len[i]-len[fa[i]])/2*sz[i];
    49     memset(ch,0,sizeof(ch));
    50     for(int i=1;i<=V;i++)ch[fa[i]][s[mi[i]+len[fa[i]]]-'a']=i;
    51     dfs(1);
    52     for(int i=1;i<=V;i++)sum[i]=sum[i-1]+l[a[i]];
    53     while (t--){
    54         scanf("%lld%lld",&k,&mod);
    55         k=k*ans%mod+1;
    56         int p=lower_bound(sum+1,sum+V+1,k)-sum;
    57         k-=sum[p-1];
    58         p=a[p];
    59         int x=len[fa[p]]+1,y=len[p];
    60         while (x<y){
    61             int mid=(x+y>>1);
    62             if ((mid+len[fa[p]]+1LL)*(mid-len[fa[p]])/2*sz[p]>=k)y=mid;
    63             else x=mid+1;
    64         }
    65         k-=(x+len[fa[p]])*(x-1LL-len[fa[p]])/2*sz[p];
    66         printf("%c\n",s[(k-1)%x+mi[p]]);
    67         ans+=s[(k-1)%x+mi[p]];
    68     }
    69 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11254575.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/728b29b22d1f4ed2b828012c0f9a09ac.png