题解：P4143 采集矿石

· · 题解

Solution

感觉这道题后缀树上倍增的做法会比较好理解，同时时间复杂度也更优。

这里讲一下后缀树吧，后缀树其实就是字符串中的所有子串组成的 \text{Trie} 上每个后缀对应的节点构成的虚树，所以建后缀树就和建虚树方式差不多，众所周知，建虚树时我们要先对所有节点按 \text{dfs} 序排序，并对相邻节点求 \text{LCA}，后缀树上的 \text{dfs} 序大小关系就是对应的字符串的字典序大小关系，\text{LCA} 就为 \text{lcp}，所以我们先对这个字符串跑一遍后缀数组，然后按字典序依次加入每个后缀，并用一个单调栈维护当前的后缀树上最右边的链即可，具体实现可以看一下代码。

然后考虑这个题怎么做，注意到当左端点固定，右端点向右移动时，字典序的降序排名单调递增，这段矿石的重要度之和单调不降，所以右端点显然是有单调性的，先在后缀树上 \text{dfs} 一遍求出所有节点的字典序排名，然后枚举左端点，在后缀树上这个后缀对应的节点到根的链上倍增跳即可，注意找到一个深度最小的满足条件的节点后，还要在这个点到这个点的父亲的边上再倍增，因为建出来的实际上是一棵虚树。

Code

//when you use vector or deque,pay attention to the size of it.
//by OldDirverTree
#include<bits/stdc++.h>
//#include<atcoder/all>
#define P pair<int,int>
#define int long long
#define mid (l+r>>1)
using namespace std;
//using namespace atcoder;
const int N=1e5+2,M=2e5+1;
int rnk[M],dis[M],fa[M][18];
int sum[N],sa[N],height[N];
int n,m,tax[N],rk[N],x[N];
char s[N]; int now,stk[M];
vector<int> g[M];
vector<P> ans;

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x) {
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30) )*0xbf58476d1ce4e5b9;
        x=(x^(x>>27) )*0x94d049bb133111eb;
        return x^(x>>31);
    }
    size_t operator() (uint64_t x) const {
        static const uint64_t FIXED_RANDOM=chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};
int read() {
    int x=0; bool f=true; char c=0;
    while (!isdigit(c) ) f&=(c!='-'),c=getchar();
    while (isdigit(c) ) x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?x:-x;
}
void SA()
{
    for (int i=1;i<=n;i++) tax[rk[i]=s[i] ]++;
    for (int i=2;i<=m;i++) tax[i]+=tax[i-1];
    for (int i=n;i;i--) sa[tax[rk[i] ]--]=i;
    for (int l=1;l<=n;l<<=1)
    {
        int len=0; for (int i=n-l+1;i<=n;i++) x[++len]=i;
        for (int i=1;i<=n;i++) if (sa[i]>l) x[++len]=sa[i]-l;
        for (int i=1;i<=m;i++) tax[i]=0;
        for (int i=1;i<=n;i++) tax[rk[i] ]++;
        for (int i=2;i<=m;i++) tax[i]+=tax[i-1];
        for (int i=n;i;i--) sa[tax[rk[x[i] ] ]--]=x[i];
        swap(rk,x),rk[sa[1] ]=1,m=1; for (int i=2;i<=n;i++)
        if (x[sa[i] ]==x[sa[i-1] ]&&x[sa[i]+l]==x[sa[i-1]+l]) rk[sa[i] ]=m;
        else rk[sa[i] ]=++m; if (m==n) break;
    }
    for (int i=1,k=0;i<=n;i++) {
        if (rk[i]==1) continue; if (k) k--; int j=sa[rk[i]-1];
        while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++; height[rk[i] ]=k;
    }
}
void build()
{
    vector<int> pos; //保证子节点间的字典序大小关系
    int cnt=n+1,top=1; stk[1]=n+1; //令根节点为 n+1
    for (int i=1;i<=n;i++) {
        while (dis[stk[top] ]>height[i]) top--;
        if (dis[stk[top] ]==height[i]) fa[i][0]=stk[top],dis[i]=n-sa[i]+1,stk[++top]=i,pos.push_back(i);
        else fa[++cnt][0]=stk[top],dis[cnt]=height[i],fa[stk[top+1] ][0]=cnt,fa[i][0]=cnt,dis[i]=n-sa[i]+1,
        stk[++top]=cnt,stk[++top]=i,pos.push_back(cnt),pos.push_back(i);
    }
    for (int x:pos) g[fa[x][0] ].push_back(x);
}
void dfs(int u) {
    for (int i=1;i<18;i++) fa[u][i]=fa[fa[u][i-1] ][i-1];
    for (int v:g[u]) now+=dis[v]-dis[u],rnk[v]=now,dfs(v);
}
main()
{
    scanf("%s",s+1),n=strlen(s+1);
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+read();
    m='z',SA(),build(),dfs(n+1);
    for (int l=1;l<=n;l++) {
        int rt=rk[l]; for (int i=17;~i;i--)
        if (fa[rt][i]&&sum[l+dis[fa[rt][i] ]-1]-sum[l-1]>=now-rnk[fa[rt][i] ]+1)
        rt=fa[rt][i]; int pos=l+dis[rt]-1,nowrk=now-rnk[rt]+1; for (int i=17;~i;i--)
        if (pos-(1<<i)>=l+dis[fa[rt][0] ]&&sum[pos-(1<<i)]-sum[l-1]>=nowrk+(1<<i) )
        pos-=1<<i,nowrk+=1<<i; if (sum[pos]-sum[l-1]==nowrk) ans.push_back({l,pos});
    }
    printf("%d",ans.size() );
    for (auto [l,r]:ans) printf("\n%d %d",l,r);
    return 0;
}