HDU-6704 K-th occurrence (后缀自动机father树上倍增建权值线段树合并)

Diposting di

传送门

题意

给出一个长度为$n$字符串$s$， $m$次询问，每次问你字符串$s$区间内的字符串$l,r$第$k$次出现的位置。

思路

比赛的时候一眼就知道是$sa$但是对于$sa$实在不喜欢，于是比赛的时候整场用$sam$硬怼。已经想到了用主席树记录$endpos$位置，然后从后往前推过去，但是比赛时还不会在$sam$上玩权值线段树合并，赛后学习了一下。

首先，这题我们可以在$sam$上的每个新开节点上存储这个节点是在原串的那个位置是把。

然后对于一个串$i​$他的$father​$肯定是他的$后缀​$ 所以他的$endpos​$肯定也是他$father​$的$endpos​$

同时一个$father$不仅仅只有$i$这个儿子 所以$father$的继承是从很多儿子那边的来的，于是我们需要搞笑处理继承效果，这里用到了权值线段树合并,线段树下标是$endpos$在$s$的位置。

这样我们就可以通过找到一个点而得出这个点所有的$endpos$ ，也可以很快的在权值线段树中找到第$k$大的$endpos $。但是$Q$次查询每次都可能用一个长度$1e5$的串进入$sam$中找这个点的位置，于是我们考虑离线操作，将询问按照$r$排序。但是我们找到了一个点之后可能这个长度太大了，于是我们需要跳到这个点的$father$ 知道这个点的长度刚好大于等于我们需要的长度，这样答案才完整。因为$father$的长度是单调的，于是我们可以考虑用树上倍增 快速找到合适的$father$。

于是这题就愉快的结束了。真爽啊。debug都不需要。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=5e5+50;
int ls[maxn*80],rs[maxn*80],rt[maxn*80],sum[maxn*80],cnt;
void update(int &o,int l,int r,int pos){
    if(!o)o=++cnt;
    if(l==r){
        sum[o]++;return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)update(ls[o],l,mid,pos);
    else update(rs[o],mid+1,r,pos);
    sum[o]=sum[ls[o]]+sum[rs[o]];
}
int merger(int o,int pre,int l,int r){
    if(!o)return pre;if(!pre)return o;
    int k=++cnt;
    if(l==r){
        sum[k]=sum[o]+sum[pre];
        return k;
    }int mid=(l+r)/2;
    ls[k]=merger(ls[o],ls[pre],l,mid);
    rs[k]=merger(rs[o],rs[pre],mid+1,r);
    sum[k]=sum[ls[k]]+sum[rs[k]];
    return k;
}
int query(int o,int l,int r,int k){
    if(sum[o]<k)return -1;
    if(l==r)return l;
    int mid=(l+r)/2;
    if(sum[ls[o]]>=k)return query(ls[o],l,mid,k);
    else return query(rs[o],mid+1,r,k-sum[ls[o]]);
}
struct Q{
    int l,r,k,id;
    bool operator<(const Q &o)const{
        return r<o.r;
    }
}my[maxn];
int n;
char s[maxn];
int ans[maxn];
struct SAM{
    int fa[maxn],ch[maxn][26],maxlen[maxn],tot,last;
    int sz[maxn],a[maxn],b[maxn];
    void init(){
        cnt=0;
        fill(rt,rt+n*80,0);
        fill(ls,ls+n*80,0);
        fill(rs,rs+n*80,0);
        fill(sum,sum+n*80,0);
        tot=last=1;maxlen[1]=fa[1]=0;
        memset(ch[1],0,sizeof(ch[1]));
    }
    void add(int x,int id){
        int np=++tot,p=last;last=np;update(rt[np],1,n,id);
        maxlen[np]=maxlen[p]+1;sz[np]=1;
        memset(ch[np],0,sizeof(ch[np]));
        while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
        if(!p)fa[np]=1;
        else{
            int q=ch[p][x];
            if(maxlen[q]==maxlen[p]+1)fa[np]=q;
            else{
                int nq=++tot;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[np]=fa[q]=nq;
                maxlen[nq]=maxlen[p]+1;
                while(p&&ch[p][x]==q)ch[p][x]=nq,p=fa[p];
            }
        }
    }
    int pa[maxn][25];
    void Sort(){///拓扑排序 得到每个集合里的串出现次数
        for(int i=1;i<=tot;i++)a[i]=0;
        for(int i=1;i<=tot;i++)a[maxlen[i]]++;
        for(int i=1;i<=tot;i++)a[i]+=a[i-1];
        for(int i=1;i<=tot;i++)b[a[maxlen[i]]--]=i;
        for(int i=tot;i;i--)sz[fa[b[i]]]+=sz[b[i]];
        for(int i=tot;i;i--){
            int k=b[i];
            pa[k][0]=fa[k];
            rt[fa[k]]=merger(rt[fa[k]],rt[k],1,n);
        }
        for(int i=1;i<=20;i++){
            for(int j=1;j<=tot;j++){
                int v=pa[j][i-1];
                pa[j][i]=pa[v][i-1];
            }
        }
    }
    int go(int id,int len){
        for(int i=20;i>=0;i--){
            if(maxlen[pa[id][i]]>=len)id=pa[id][i];
        }
        return id;
    }
    int m;
    void slove(){
        for(int i=1;i<=m;i++){
            cin>>my[i].l>>my[i].r>>my[i].k;
            my[i].id=i;
        }
        sort(my+1,my+1+m);
        int now=1;
        int tail=1;
        for(int i=1;i<=n;i++){
            int x=s[i]-'a';
            now=ch[now][x];
            while(tail<=m&&my[tail].r==i){
                int len=my[tail].r-my[tail].l+1;
                int where=go(now,len);
                int aa=query(rt[where],1,n,my[tail].k);
                if(aa==-1)ans[my[tail].id]=-1;
                else{
                    ans[my[tail].id]=aa-len+1;
                }
                tail++;
            }
        }
        for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
    }
}S;
int main()
{
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n;cin>>S.m;
        cin>>s+1;
        n=strlen(s+1);S.init();
        for(int i=1;i<=n;i++)S.add(s[i]-'a',i);
        S.Sort();
        S.slove();
    }
    return 0;
}