题解 P6385 【『MdOI R2』Little Goth】

· · 题解

终于有一个不是 Ynoi 的月赛 F 题了，是不是很感动

若无特别说明，i，j 和 k 表示小 M 的位置，小 B 的位置和山顶的位置。操作串表示进行操作三时的 S_{i \cdots j}。

过于显然的结论不说明了，需要详细题解请报讲评

结论 -1

在所有合法的 j 中，选取最大的作为小 B 的初始位置一定不劣。

结论 0

任何时候，假如满足 i=j，在接下来的过程中保持 i=j 一定不劣。

结论 1

假如存在一种方案，使得在进行第一次操作三时，操作串不是给定的 S_{i \cdots j} 的子串，且优于一切不是这样的方案，那么这个方案一定不优于先使 i=j，然后再进行操作。

证明 1

注意到，在这种方案中，你一定在第一次操作三之前使用了 i-1 或者 j+1。

假如你使用了上述操作，并且在第一次操作三时的 i,j 与给定的 i,j 有交，那么你把上述操作移动到这次操作三之后同样合法，可以变为不是这样的方案。

因为这样进行操作三时的操作串是原来的操作串的子串，因此这个操作三也合法，然后位置的差别可以通过在之后进行同样的操作来修正。

假如操作串与输入的 S_{i \cdots j} 没有交，但多于一个字符，撤销掉若干个上述操作一定可以让它变成一个字符，然后把撤销掉的这些操作移动到最后一定也合法。

这个结论可以归纳地推广到任意一次操作三。

至此，我们可以先处理两种情况：不使用操作三，以及先通过某些操作使得 i=j 然后保持这样。

不使用操作三时，答案为 |i-k|。

考虑单字符的情况：记 dis_{i,j} 表示从 j 到任意一个 x 使得 S_x = i 的最小代价。考虑如何计算，枚举字符 i ，然后将所有字符为 i 的位置加入队列，进行多源 bfs 即可。暴力实现会建出 O(n^2) 条边，可以使用一个优化建图技巧：对每个字符建一个虚点，每个位置向对应字符连 1 边，字符向位置连 0 边，跑 01-bfs。也有等价的不需要显式地优化建图的方法。

然后，枚举第一次操作三时的字符 c。第一种情况是，c 在 S_{i \cdots j} 中出现过，可以用 j-i+dis_{c,k}+1 更新答案。

第二种情况是 c 没有出现过，此时用 j-i+ \min(dis_{c,i},dis_{c,j})+dis_{c,k}+1 更新答案。

在后面，我们只考虑，进行操作三时的操作串是 S_{i \cdots j} 的子串的情况。其他情况已经处理过了。

结论 2

一定存在一种最优解的方案是，先进行若干次操作一和操作二，然后进行一次操作三，然后再进行若干次操作一。

简要说明一下：考虑假如你在两次操作三之间进行了一次其他操作，将这个操作移到所有操作三的前面也是合法的。

这样的话，所有操作三是连续的一段，显然可以只进行一次。

因此：这种情况是，先收缩成一段，然后进行一次操作三，然后归位。

我们考虑操作三之后 i 与 k 的位置关系。

第一种情况是 i<k。发现这样一定不优于让 i=k。

因为，这样操作之后需要进行若干次操作使 i+1，而如果将这些操作放在操作三之前完成，也是合法的。

第二种情况是 i \geq k。

把答案写出来，然后去掉常数，发现我们要做的其实是，对于所有在 k 之后出现过的 [L,R] ，满足 S_{L \cdots R} 在 S_{i \cdots j} 中出现过，最小化 2L-R。

暴力1

固定 L 时，显然 R 应该尽量大。考虑枚举 L，就是求最大的 R 使得 S_{L \cdots R} 在 S_{i \cdots j} 中出现过。这个有很多种 SAM，SA，后缀树的处理方式，下面给出一种。

二分 R，即判断 S_{L \cdots R} 是否存在于 S_{i \cdots j} 中。对 S 建后缀树，倍增定位出 S_{L \cdots R}，然后求对应节点的子树中是否存在在 [i+R-L,j] 中的后缀即可。这一步可以可持久化线段树合并。

算上枚举 L，总复杂度 O(nq\log^2n)。然而标算使用的是略为复杂的 O(nq\log n) 的离线 LCT 做法。

暴力2

固定长度，则 L 应尽量小。

首先考虑 k 固定的情况，发现求出的 j 是两个后缀的 LCP，也就是说，S_{i \cdots j} 是后缀树上一个节点，是 SAM 上的一个等价类。

对每个点维护子树中的所有在 k 之后最左的后缀。我们在后缀树上 dp，设 f_i 为节点 i 代表的子串的所有子串的 2L-R 的最小值，g_i 表示节点 i 的子树中的 k 之后的最左的后缀的位置，len_i 表示节点 i 代表的串的长度。

有 f_i = \min(f_{fa_i},f_{link_i},g_i - len_i -1) ，其中 fa_i 表示节点 i 的父节点，link_i 表示节点 i 的后缀链接指向的节点。在后缀树上倍增定位出 S_{i \cdots j} 查询 dp 值即可。

注意到这样只能找到一个等价类内最长串的答案，易知这不劣。

对每个 k 做一次的复杂度为 O(n)。直接做复杂度为 复杂度 O(nq)。

不暴力了

相信各位经验丰富的选手看到这里时，正解已经呼之欲出了。

考虑用上述两个暴力来摊平查询的复杂度。考虑按 k 从后往前扫，每隔 B 个位置重新 dp 一次，然后对于到上一次重构中间的小块部分用第一个暴力处理。

根据第一个暴力的复杂度，取适当的 B 可以得到 O(n\sqrt{n \log n}) \sim O(n\sqrt n \log n) 的做法。可以通过所有测试点。

std 写的是 O(n\sqrt{n \log n} + n \Sigma) 的做法。

下面是 std，需要可以自取

#include <bits/stdc++.h>
#define maxn 30005
const int B=40;
const int inf=1e8;
int n,q,ch[maxn<<1][2],anc[maxn<<1][17]={0},
depth[maxn<<1]={0},rank[maxn],tail=0,rk[maxn<<1],dp[maxn<<1],min[maxn<<1],tl,
ans[maxn],d[maxn<<1],vis[30],dis[27][maxn],pre[maxn<<1],fa[maxn<<1],max[maxn<<1],tag[maxn<<1],
cnt[26][maxn];
std::vector<int>rc[27];
char s[maxn];
struct Q{int i,j,p,id;}qr[maxn];
int cmp1(Q a,Q b){return a.p>b.p;}
int cmp(int a,int b){
    if (depth[a]!=depth[b])return depth[a]<depth[b];
    return d[a]<d[b];
}struct Q2{
    int l,r,p,id,k;
}q1[maxn*B];
int cmp2(Q2 a,Q2 b){return a.l>b.l;}
void cover(int x,int y){tag[x]=std::min(tag[x],y);max[x]=std::min(max[x],y);}
void pushdown(int x){
    if(ch[x][0])cover(ch[x][0],tag[x]);
    if(ch[x][1])cover(ch[x][1],tag[x]);
    tag[x]=inf;
}
int not_root(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void rotate(int x) {
    int f=fa[x],g=fa[f],l=ch[f][1]==x,c=ch[x][l^1];
    if (not_root(f)) ch[g][ch[g][1]==f]=x;
    ch[x][l^1]=f;ch[f][l]=c;
    if (c) fa[c]=f;
    fa[f]=x;fa[x]=g;
}
void spaly(int x) {
    std::stack<int>stk;
    int u=x;stk.push(u);while(not_root(u)){stk.push(fa[u]);u=fa[u];}
    while(!stk.empty()){pushdown(stk.top());stk.pop();}
    while(not_root(x)){
        rotate(x); 
        if (not_root(fa[x])&&not_root(x))
            rotate((ch[fa[x]][1]==x)!=(ch[fa[fa[x]]][1]==fa[x])?fa[x]:x);
    }
}
struct suffixTree {
    int link[maxn<<1],len[maxn<<1],start[maxn<<1],s[maxn<<1],tail,n,rem,now,ch[maxn<<1][27];
    suffixTree ():tail(1),n(0),rem(0),now(1) {len[0]=inf;}
    int newnode(int st,int le){
        link[++tail]=1;start[tail]=st;len[tail]=le;return tail;
    }
    void extend(int x){
        s[++n]=x;rem++;
        for (int last=1;rem;){
            while (rem>len[ch[now][s[n-rem+1]]]) rem-=len[now=ch[now][s[n-rem+1]]];
            int &v=ch[now][s[n-rem+1]];int c=s[start[v]+rem-1];
            if (!v||x==c){
                link[last]=now;last=now;
                if (!v) v=newnode(n-rem+1,inf);
                else break;
            }else{
                int u=newnode(start[v],rem-1);
                ch[u][c]=v;ch[u][x]=newnode(n,inf);
                start[v]+=rem-1;len[v]-=rem-1;
                link[last]=v=u;last=u;
            } if (now==1) rem--;else now=link[now];
        }
    }
}sft;

void dfs(int u,int f){
    anc[u][0]=f;
    for (int i=1;i<=15;++i)anc[u][i]=anc[anc[u][i-1]][i-1];
    int len=std::min(sft.len[u],n-sft.start[u]+1),isleaf=1;
    pre[u]=fa[u]=f;max[u]=tag[u]=inf;
    depth[u]=depth[f]+len;d[u]=d[f]+1;
    for (int i=0;i<=26;++i)
        if (sft.ch[u][i])dfs(sft.ch[u][i],u),isleaf=0;
    if (isleaf)
        rank[n-depth[u]+1]=u;
    rk[++tl]=u;
}

void access(int x,int w) {
    for (int y=0;x;x=fa[y=x])spaly(x),ch[x][1]=y,cover(x,w);
}

int query(int x,int r){
    if(!x)return 0;
    pushdown(x);
    if(max[x]<r-depth[pre[x]]+1){
        int d=query(ch[x][1],r);
        if(d)return d;else return std::min(depth[x],r-max[x]+1);
    }return query(ch[x][0],r);
}

int find(int x,int r){
    for(int y=0;x!=1&&x;x=fa[y=x]){
        spaly(x);ch[x][1]=0;
        int u=x;while(ch[u][0]){pushdown(u);u=ch[u][0];}
        if(max[u]<r-depth[pre[u]]+1)
            return query(x,r);
        ch[x][1]=y;
    }return 0;
}

void rebuild(int l){
    std::memset(dp,63,sizeof(dp));
    for(int i=l;i<=n;++i)min[rank[i]]=i;
    for(int i=tl;i>=1;i--)min[anc[rk[i]][0]]=std::min(min[rk[i]],min[anc[rk[i]][0]]);
    for(int j=2;j<=tl;++j){
        int i=rk[j];
        dp[i]=min[i]-depth[i]+1;
        dp[i]=std::min(dp[i],std::min(dp[anc[i][0]],sft.link[i]!=1?dp[sft.link[i]]:inf));
    }
} 
int locate(int l,int r){
    int u=rank[l];
    for (int i=15;i>=0;i--)
        if (depth[anc[u][i]]>=(r-l+1))u=anc[u][i];
    return u;
}int lca(int u,int v){
    if (d[u]<d[v])std::swap(u,v);
    for(int i=15;i>=0;i--)if(d[anc[u][i]]>=d[v])u=anc[u][i];
    if (u==v)return u;
    for(int i=15;i>=0;i--)if(anc[u][i]!=anc[v][i])u=anc[u][i],v=anc[v][i];
    return anc[u][0];
}   
void bfs(int c){
    std::queue<int>q;
    std::memset(vis,0,sizeof(vis));
    std::memset(dis[c],63,sizeof(dis[c]));
    for(int v:rc[c]){q.push(v);dis[c][v]=0;}
    vis[c]=1;
    while(!q.empty()){
        int x=q.front();int d=s[x]-'a';q.pop();
        if(!vis[d]){
            vis[d]=1;
            for(int v:rc[d])
                if(dis[c][v]>n){dis[c][v]=dis[c][x]+1;q.push(v);}
        }if (x>1&&dis[c][x-1]>n){dis[c][x-1]=dis[c][x]+1;q.push(x-1);}
        if(x<n&&dis[c][x+1]>n){dis[c][x+1]=dis[c][x]+1;q.push(x+1);}
    }
}
void prework(){
    std::memset(min,63,sizeof(min));
    sft.link[1]=1;dfs(1,0);std::sort(rk+1,rk+tl+1,cmp);
    for(int i=1;i<n;++i)sft.link[rank[i]]=rank[i+1];
    for(int i=1;i<=n;++i)rc[s[i]-'a'].push_back(i);
    for(int i=0;i<26;++i)bfs(i);
}
int corner_cases(int i,int j,int p){
    int ans=abs(i-p);
    for(int c=0;c<26;++c){
        ans=std::min(ans,j-i+dis[c][i]+dis[c][p]+1);
        ans=std::min(ans,j-i+dis[c][j]+dis[c][p]+1);
        if(cnt[c][j]-cnt[c][i-1])ans=std::min(ans,j-i+dis[c][p]+1);
    }return ans;
}
int main(){
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    for (int i=1;i<=n;++i){
        sft.extend(s[i]-'a');
        for(int c=0;c<26;++c)cnt[c][i]=cnt[c][i-1];
        cnt[s[i]-'a'][i]++;
    }
    sft.extend(26);prework();
    for(int i=1;i<=q;++i){
        scanf("%d%d%d",&qr[i].i,&qr[i].j,&qr[i].p);qr[i].id=i;
        int len=depth[lca(rank[qr[i].i],rank[qr[i].j])];
        qr[i].j=qr[i].i+len-1;
    }std::sort(qr+1,qr+q+1,cmp1);
    int cnt=0,last=n,p=0;
    rebuild(n);
    for(int i=n;i>=1;--i){
        cnt++;
        if (cnt>B){rebuild(i);last=i;cnt=0;}
        while(p<q&&qr[p+1].p==i){
            ++p;
            ans[qr[p].id]=
            std::min(qr[p].j-qr[p].i+1+dp[locate(qr[p].i,qr[p].j)]-qr[p].p,
            corner_cases(qr[p].i,qr[p].j,qr[p].p));
            for(int j=i;j<last;++j){
                q1[++tail].l=qr[p].i;q1[tail].r=qr[p].j;q1[tail].p=j;
                q1[tail].id=qr[p].id;
                q1[tail].k=j-i+qr[p].j-qr[p].i+2;
            }
        }
    }std::sort(q1+1,q1+tail+1,cmp2);
    p=0;
    for(int i=n;i>=1;--i){
        access(rank[i],i);
        while(p<tail&&q1[p+1].l==i){
            ++p;int d=find(rank[q1[p].p],q1[p].r);
            if(d)ans[q1[p].id]=std::min(ans[q1[p].id],q1[p].k-d);
        }
    }
    for(int i=1;i<=q;++i)ans[qr[i].id]+=n-qr[i].j; 
    for(int i=1;i<=q;++i)printf("%d\n",ans[i]);
    return 0;
}