题解洛谷 P4143 【采集矿石】

对于一个固定的左端点，右端点向右移动时，其子串权值和不断增大，字典序降序排名不断减小，因此对于一个左端点，最多存在一个右端点使其满足条件。

所以可以枚举左端点，然后二分右端点的位置，权值和通过前缀和来查询，现在的问题就是如何快速查询一个子串的排名。

考虑用后缀数组来解决，对于一个子串\([l,r]\)，对于在位置\(l\)对应的后缀排名之前的后缀中的子串是能对该子串的排名产生贡献的。

若该子串的长度比\(l\)对应的后缀和前一个后缀的\(LCP\)大，即\(len>ht_{rk_l}\)，也就是该子串没有被\(LCP\)所包括，则其排名为\(sum_l-(n-l+1-len)\)，其中\(sum_l\)表示\(l\)所对应的后缀之前所有的后缀中本质不同的子串个数，然后再减去右端点\(r\)右边多算的部分，即为该子串的排名。然后求降序排名时，用本质不同子串个数减去正序排名即可。

若该子串被\(LCP\)所包括，那么直接像上面那样计算是不对的，则需向前二分到第一个和\(l\)所对应的后缀的\(LCP\)恰好等于\(len\)的位置，然后和上面一样用该位置计算排名。

最终的复杂度为\(O(n\ log^2\ n)\)

\(code:\)

#include<bits/stdc++.h>

#define maxn 400010

#define mk make_pair

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

ll n,m,ans,tot;

int v[maxn],b[maxn],rk[maxn],sa[maxn],tp[maxn],ht[maxn];

int lg[maxn],f[maxn][25];

ll sum[maxn];

char s[maxn];

vector<pair<int,int> > ve;

void rsort()

{

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

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

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

    for(int i=n;i;--i) sa[b[rk[tp[i]]]--]=tp[i];

}

void SA()

{

    for(int i=1;i<=n;++i) rk[i]=s[i],tp[i]=i;

    rsort();

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

    {

        int num=0;

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

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

            if(sa[i]>k)

                tp[++num]=sa[i]-k;

        rsort(),memcpy(tp,rk,sizeof(rk)),rk[sa[1]]=num=1;

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

            rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?num:++num;

        if(num==n) break;

        m=num;

    }

    int k=0;

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

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

    {

        if(rk[i]==1) continue;

        if(k) k--;

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

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

        ht[rk[i]]=k;

    }

    tot=n*(n+1)/2;

    for(int i=1;i<=n;++i) tot-=ht[i];

    sum[sa[1]]=n-sa[1]+1;

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

        sum[sa[i]]=sum[sa[i-1]]+n-sa[i]+1-ht[i];

}

void init()

{

    lg[0]=-1;

    for(int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;

    for(int i=1;i<=n;++i) f[i][0]=ht[i];

    for(int j=1;j<=20;++j)

        for(int i=1;i+(1<<j)-1<=n;++i)

            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);

}

int lcp(int l,int r)

{

    if(l>r) swap(l,r);

    l++;

    int len=lg[r-l+1];

    return min(f[l][len],f[r-(1<<len)+1][len]);

}

ll get(int L,int R)

{

    int len=R-L+1;

    if(len>ht[rk[L]]) return tot-(sum[L]-(n-L+1-len))+1;

    else

    {

        int l=1,r=rk[L]-1,p;

        while(l<=r)

        {

            int mid=(l+r)>>1;

            if(lcp(rk[L],mid)>=len) p=mid,r=mid-1;

            else l=mid+1;

        }

        return tot-(sum[sa[p]]-(n-sa[p]+1-len))+1;

    }

}

void work()

{

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

    {

        int l=i,r=n;

        while(l<=r)

        {

            int mid=(l+r)>>1;

            ll rank=get(i,mid),val=v[mid]-v[i-1];

            if(rank==val)

            {

                ans++,ve.push_back(mk(i,mid));

                break;

            }

            else if(rank>val) l=mid+1;

            else r=mid-1;

        }

    }

}

int main()

{

    scanf("%s",s+1),n=strlen(s+1),m=150;

    for(int i=1;i<=n;++i) read(v[i]),v[i]+=v[i-1];

    SA(),init(),work();

    printf("%d\n",ans),sort(ve.begin(),ve.end());

    for(int i=0;i<ve.size();++i)

        printf("%d %d\n",ve[i].first,ve[i].second);

    return 0;

}

巴特西

题解洛谷 P4143 【采集矿石】

最新文章

热门文章

巴特西

题解 洛谷 P4143 【采集矿石】

最新文章

热门文章

题解洛谷 P4143 【采集矿石】