K-th occurrence HDU - 6704 (后缀数组+二分线段树+主席树)

大意: 给定串s, q个询问(l,r,k), 求子串s[l,r]的第kk次出现位置.

这是一篇很好的题解：

https://blog.csdn.net/sdauguanweihong/article/details/100063096

加点个人：

我对上面的题解更为详细的解释下：

后缀数组处理出来的heigth[] 数组有个这样的性质：

对于排名 a 的后缀字符串与排名 b 的后缀字符串，他们的最长公共前缀的长度为 min{heigth[a+1],heigth[a+2],heigth[b]};

依据这样的性质就可以二分线段树出[l,r] 这个字符串是在多少排名的区间[L,R]了；

注意：我本想贪图方便用先二分l然后判断[l,pos] 的最小值复杂度为log*log 这个会T的

所以找这个区间要用log的方法，就是在存了最小值的线段树里面去搜左孩子啊右孩子什么的

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn = ;

char s[maxn];

int y[maxn],x[maxn],c[maxn],sa[maxn],rk[maxn],height[maxn],wt[];

int n,k,q;

int get_SA(int m){

    for(int i= ; i<=m ; i++) c[i]=;

    for(int i= ; i<=n ; i++) sa[i]=;

    for(int i= ; i<=n ; i++) ++c[x[i]=s[i]];

    for(int i= ; i<=m ; i++) c[i]+=c[i-];

    for(int i=n ; i>= ; i--) sa[c[x[i]]--]=i;

    for(int k= ; k<=n ; k<<=){

        int num=;

        for(int i=n-k+ ; i<=n ; i++) y[++num]=i;

        for(int i= ; i<=n ; i++) if(sa[i]>k) y[++num]=sa[i]-k;

        for(int i= ; i<=m ; i++) c[i]=;

        for(int i= ; i<=n ; i++) ++c[x[i]];

        for(int i= ; i<=m ; i++) c[i]+=c[i-];

        for(int i=n ; i>= ; i--) sa[c[x[y[i]]]--]=y[i],y[i]=;

        swap(x,y);

        x[sa[]]=;

        num=;

        for(int i= ; i<=n ; i++)

            x[sa[i]]=(y[sa[i]]==y[sa[i-]] && y[sa[i]+k]==y[sa[i-]+k]) ? num : ++num;

            if (num==n) break;

            m=num;

    }

}

int get_height() {

    int k=;

    for (int i=; i<=n; ++i) rk[sa[i]]=i;

    for (int i=; i<=n; ++i) {

        if (rk[i]==) continue;

        if (k) --k;

        int j=sa[rk[i]-];

        while (j+k<=n && i+k<=n && s[i+k]==s[j+k]) ++k;

        height[rk[i]]=k;

    }

}

int mi[maxn<<];

void pushup(int rt){

    mi[rt]=min(mi[rt<<],mi[rt<<|]);

}

void build(int l,int r,int rt)

{

    if ( l==r )

    {

        mi[rt]=height[l];

        return ;

    }

    int m = (l+r) >> ;

    build(l,m,rt<<);

    build(m+,r,rt<<|);

    pushup(rt);

}

int solvel(int o , int l , int r , int x , int v){

    int mid=(l+r)>>;

    if(r<=x){

        if(l==r) return mi[o]>=v?l:-;

        if(mi[o<<|]<v) return solvel(o<<|,mid+,r,x,v);

        int t=solvel(o<<,l,mid,x,v);

        return t==-?mid+:t;

    }

    if(mid>=x) return solvel(o<<,l,mid,x,v);

    int R=solvel(o<<|,mid+,r,x,v);

    if (R==-||R>mid+) return R;

    int L = solvel(o<<,l,mid,x,v);

    return L==-?R:L;

}

int solver(int o, int l, int r, int x, int v){

    int mid=(l+r)>>;

    if (x<=l) {

        if (l==r) return mi[o]>=v?l:-;

        if (mi[o<<]<v) return solver(o<<,l,mid,x,v);

        int t = solver(o<<|,mid+,r,x,v);

        return t==-?mid:t;

    }

    if (mid<x) return solver(o<<|,mid+,r,x,v);

    int L = solver(o<<,l,mid,x,v);

    if (L==-||L<mid) return L;

    int R = solver(o<<|,mid+,r,x,v);

    return R==-?L:R;

}

int tot;

int lson[maxn<<],rson[maxn<<],T[maxn],cc[maxn<<];

void zhu_build(int &root,int l,int r)

{

    root=++tot;

    if ( l==r ) return;

    int mid=(l+r)/;

    zhu_build(lson[root],l,mid);

    zhu_build(rson[root],mid+,r);

}

void update(int root,int &rt,int p,int val,int l,int r)

{

    rt=++tot;

    lson[rt]=lson[root],rson[rt]=rson[root];

    cc[rt]=cc[root]+val;

    if ( l==r ) return;

    int mid=(l+r)/;

    if ( p<=mid ) update(lson[rt],lson[rt],p,val,l,mid);

    else update(rson[rt],rson[rt],p,val,mid+,r);

}

int query(int rt_,int rt,int l,int r,int k)

{

    if ( l==r ) return l;

    int mid=(l+r)/;

    int sum=cc[lson[rt_]]-cc[lson[rt]];

    if ( sum>=k ) return query(lson[rt_],lson[rt],l,mid,k);

    else return query(rson[rt_],rson[rt],mid+,r,k-sum);

}

int main(){

    int _;scanf("%d",&_);

    while(_--){

    scanf("%d%d%s",&n,&q,s+);

    get_SA();

    get_height();

    build(,n,);

    tot=;

    zhu_build(T[],,n);

    for(int i= ; i<=n ; i++){

        update(T[i-],T[i],sa[i],,,n);

    }

    while(q--){

        int l,r;scanf("%d%d%d",&l,&r,&k);

        int p=rk[l];

    int ql = p>?solvel(,,n,p,r-l+)-:;

    int qr = p<n?solver(,,n,p+,r-l+):n;

    if (ql<) ql = p;

    if (qr<) qr = p;

        int ans;

        if(qr-ql+<k)

        ans=-;

        else

        ans=query(T[qr],T[ql-],,n,k);

        printf("%d\n",ans);

    }

    }

}

巴特西

K-th occurrence HDU - 6704 (后缀数组+二分线段树+主席树)

最新文章

热门文章