K-th occurrence 2019CCPC网络赛+HDU6704（后缀自动机+主席树）

K-th occurrence

之前网络赛跟队友合体出的题，当时我写的后缀自动机，他写的主席树，hhh！
现在我会写主席树，他会写后缀数组，于是各自独立的A了！并且我跟之前网络赛时的解法还不完全一样
巨佬队友bxd的后缀数组+主席树解法

题意：

给定一个串 $S$ ，有 $Q$ 个询问：求子串 $S [l, r]$ 在 $S$ 中的第 $k$ 次出现位置。

思路：

由于后缀自动机可以知道某个子串的 $e n d p o s$ 集合，显然此题至少有暴力的做法。
首先，得找到最短的包含所询问的子串的节点，然后其所在 $p a r e n t$ $t r e e$ 的子树就是所有 $e n d p o s$ 的集合。那么，如何快速找到这个节点呢？在构建后缀自动机时考虑每插入一个字符，就记录下这个节点所代表的最长子串属于对应字符串的哪个位置，并进行双向链接。通过 $r$ 的这个链接就可以找到那个节点；找到后通过倍增就可以在 $O (l o g n)$ 时间内找到这个最短的包含所询问的子串的节点。
然后如何处理子树中第 $k$ 小权值呢？一个常见套路就是在树的 $d f s$ 序上建主席树！ $T h e n$ ，问题基本得到解决。
有个细节就是判断什么条件输出 $- 1$ ，这里有两种处理：
处理 $1$ ：我们想要的是那个子树的节点数大于等于 $k$ 即可，但是考虑到虚点的存在，我们再 $d f s$ 序上建主席树时，不要插入虚点即可。
处理 $2$ ：计算每个节点的 $c n t$ 值，然后提前判断找到的节点的 $c n t$ 值是否大于等于 $k$ 即可。（这是比赛时的做法）

刚刚写好的代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 2e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

char s[maxn];
int N, Q;
int ch[maxn][26], len[maxn], endpos[maxn], rpos[maxn];
int last, tot;
int fa[maxn], st[maxn][18];
int head[maxn], to[maxn], nxt[maxn], edge;
int id[maxn], rk[maxn], sz[maxn], ID;
int rt[maxn], node[maxn<<5], ls[maxn<<5], rs[maxn<<5], cnt;

inline void add_edge(int u, int v) {
    ++edge; to[edge]=v; nxt[edge]=head[u]; head[u]=edge;
}

void add(int c) {
    int p=last, np=last=++tot;
    rpos[endpos[np]=len[np]=len[p]+1]=np;
    for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=st[np][0]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=st[np][0]=q;
        else {
            int nq=++tot; len[nq]=len[p]+1;
            st[nq][0]=fa[nq]=fa[q]; st[q][0]=st[np][0]=fa[q]=fa[np]=nq;
            memcpy(ch[nq],ch[q],104);
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
            endpos[nq]=0;
        }
    }
}

void dfs(int u) {
    rk[id[u]=++ID]=u; sz[u]=1;
    for(int i=head[u]; i; i=nxt[i]) dfs(to[i]), sz[u]+=sz[to[i]];
}

int get_pos(int length, int r) {
    int x=rpos[r];
    for(int i=17; i>=0; --i) if(len[st[x][i]]>=length) x=st[x][i];
    return x;
}

void update(int x, int l, int r, int pre, int &now) {
    now=++cnt;
    node[now]=node[pre]+1; ls[now]=ls[pre]; rs[now]=rs[pre];
    if(l==r) return;
    int m=(l+r)/2;
    if(x<=m) update(x,l,m,ls[pre],ls[now]);
    else update(x,m+1,r,rs[pre],rs[now]);
}

int query(int k, int l, int r, int x, int y) {
    if(l==r) return l;
    int s=node[y]-node[x], sl=node[ls[y]]-node[ls[x]];
    if(s<k) return -1;
    int m=(l+r)/2;
    if(sl>=k) return query(k,l,m,ls[x],ls[y]);
    return query(k-sl,m+1,r,rs[x],rs[y]);
}

int main() {
    int T=read();
    while(T--) {
        last=tot=1;
        N=read(), Q=read();
        scanf("%s", s+1);
        for(int i=1; s[i]; ++i) add(s[i]-'a');
        for(int i=2; i<=tot; ++i) add_edge(fa[i],i);
        dfs(1);
        for(int j=1; j<18; j++)
            for(int i=1; i<=tot; ++i) st[i][j]=st[st[i][j-1]][j-1];
        for(int i=1; i<=tot; ++i) {
            if(endpos[rk[i]]) update(endpos[rk[i]],1,N,rt[i-1],rt[i]);
            else rt[i]=rt[i-1];
        }
        while(Q--) {
            int l=read(), r=read(), k=read();
            int p=get_pos(r-l+1,r);
            int ans=query(k,1,N,rt[id[p]-1],rt[id[p]-1+sz[p]]);
            if(ans==-1) printf("-1\n");
            else printf("%d\n", ans-r+l);
        }
        for(int i=1; i<=tot; ++i) memset(ch[i],0,sizeof(ch[i])), head[i]=0;
        cnt=ID=edge=0;
    }
}

比赛时写的代码

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int N = 2e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

struct Edge{int to, nex;}edge[N];

int t[N<<5],node[N],id[N],dep[N],fa[N],top[N],son[N],siz[N],ncnt,w[N],pos,head[N],n,m,ans,lson[N<<5],rson[N<<5],T[N],tot;

char s[N];
int ch[N][26], len[N], rk[N], endpos[N];
int par[N][20];
int last, sz;
int c[N], a[N], cnt[N], lg[N];
int NN, Q, l, r, k;

inline void add(int a, int b) { edge[++pos].nex=head[a]; edge[pos].to=b; head[a]=pos; }

////////////////////
void build(int l,int r,int &pos)
{
    pos=++ncnt;
    t[pos]=0;
    if(l==r)return ;
    int m=(l+r)>>1;
    build(l,m,lson[pos]);
    build(m+1,r,rson[pos]);
}


void up(int x,int l,int r,int pre,int &pos)
{
    pos=++ncnt;
    lson[pos]=lson[pre];rson[pos]=rson[pre];
    t[pos]=t[pre]+1;
    if(l==r)return ;int m=(l+r)>>1;
    if(x<=m)up(x,l,m,lson[pre],lson[pos]);
    else up(x,m+1,r,rson[pre],rson[pos]);
}
int qk(int k,int l,int r,int pre,int pos)
{
    int x=t[lson[pos]]-t[lson[pre]];
    if(l==r)return l;
    int m=(l+r)>>1;
    if(k<=x)return qk(k,l,m,lson[pre],lson[pos]);
    else return qk(k-x,m+1,r,rson[pre],rson[pos]);
}

void dfs1(int x,int f)
{
    fa[x]=f;dep[x]=dep[fa[x]]+1;son[x]=0;siz[x]=1;
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(v==fa[x])continue;
        dfs1(v,x);siz[x]+=siz[v];
        if(siz[son[x]]<siz[v])son[x]=v;
    }
}
void dfs2(int x,int topf)
{
    top[x]=topf;id[x]=++tot;

    up(endpos[x],1,NN,T[id[x]-1],T[id[x]]);

    if(son[x])dfs2(son[x],topf);
    for(int i=head[x];i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(v==son[x]||v==fa[x])continue;
        dfs2(v,v);
    }
}
////////////////

void add_p(int c, int pos) {
    int p=last, np=last=++sz;
    len[np]=len[p]+1, cnt[np]=1, endpos[np]=pos, rk[pos]=np;
    for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++sz; endpos[nq]=NN;
            fa[nq]=fa[q], len[nq]=len[p]+1;
            memcpy(ch[nq],ch[q],104);
            fa[q]=fa[np]=nq;
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

void solve(int l, int r, int k) {
    int p=rk[r], nl=r-l+1;

    //while(p&&len[fa[p]]>=nl) p=fa[p];
    for(int i=19; i>=0; --i) {
        if(len[par[p][i]]>=nl) {
            p=par[p][i];
        }
    }
    if(cnt[p]<k) printf("-1\n");
    else {
        printf("%d\n", qk(k,1,NN,T[id[p]-1],T[id[p]+siz[p]-1])-nl+1);
    }
}

int main() {
    //ios::sync_with_stdio(false);
    for(int i=1; i<N; ++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    int TT=read();
    while(TT--) {
        NN=read(), Q=read();
        scanf("%s", s+1);
        //reverse(s+1,s+1+NN);

        last=sz=1;
        ncnt=tot=pos=0;
        build(1,NN,T[0]);

        for(int i=1; i<=NN; ++i) add_p(s[i]-'a',i);

        for(int i=1; i<=sz; ++i) c[len[i]]++;
        for(int i=1; i<=sz; ++i) c[i]+=c[i-1];
        for(int i=1; i<=sz; ++i) a[c[len[i]]--]=i;
        for(int i=sz; i; --i) cnt[fa[a[i]]]+=cnt[a[i]]; cnt[1]=0;
        for(int i=1; i<=sz; ++i) {
            add(fa[i],i);
        }
        endpos[1]=endpos[0]=NN;

        dfs1(1,0);
        dfs2(1,1);

        for(int i=1; i<=sz; ++i) par[i][0]=fa[i];
        for(int k=1; k<20; ++k)
            for(int i=1; i<=sz; ++i)
                par[a[i]][k]=par[par[a[i]][k-1]][k-1];
        while(Q--) {
            l=read(), r=read(), k=read();
            solve(l,r,k);
        }
        for(int i=0; i<=sz; ++i) {
            c[i]=a[i]=len[i]=fa[i]=cnt[i]=rk[i]=endpos[i]=head[i]=0;
            for(int j=0; j<26; ++j) ch[i][j]=0;
            for(int j=0; j<20; ++j) par[i][j]=0;
        }
    }
}