自动搬运

查看原文

来自洛谷，原作者为

	EternalAlexander 魔力的碎片都不再拥有的少年

搬运于2025-08-24 22:20:18，当前版本为作者最后更新于2020-04-15 20:14:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

终于有一个不是 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;
}