自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 23:07:02，当前版本为作者最后更新于2025-01-28 23:28:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

建出 SA，枚举长度 $x$。

对于每个子串的等价类维护一个 $a_i$ 递增集合。

如果 SA 之后相邻两个后缀的 lcp 为 $x$，即对于所有长度小于等于 $x$ 的子串这两个位置开始的均相同，那么需要合并并修改递增集合。

考虑启发式合并，每次加入先判断是否是前缀最大值，然后将后面的小于他的 erase。注意别让你的指针失效了，有一位 APIO 斩获 115 分的选手在 WC 考场上因为这件事挂分痛失 AK。

总复杂度 $O(n\log^2n)$。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
set<pair<int,int>> st[100005];
int fd[100005];
int find(int i){
	return fd[i]==i?fd[i]:fd[i]=find(fd[i]);
}
string s; int n,a[100005];
int f[100005][20],len,ord[100005],rpos[100005],reml[100005];
vector<pair<int,int>> v1[100005],v2[100005];
int lcp(int i,int j){
	int ret=0;
	for(int k=19;k>=0;k--){
		if(i>=(1<<k)&&j>=(1<<k)){
			if(f[i][k]==f[j][k]){
				ret+=(1<<k);
				i-=(1<<k);
				j-=(1<<k);
			}
		}
	}
	return ret;
}
int ans[100005];
signed main(){
	cin>>s; n=s.size(); s=" "+s;
	for(int i=1;i<=n;i++) cin>>a[i],fd[i]=i;
	for(int i=1;i<=n;i++) f[i][0]=s[i]-'a'+1; len=26;
	for(int i=1;i<=19;i++){
		for(int j=0;j<=max(len,n);j++) v1[j].clear(),v2[j].clear();
		for(int j=1;j<=n;j++) if(j<=(1<<(i-1))) v1[0].push_back(make_pair(f[j][i-1],j)); else v1[f[j-(1<<(i-1))][i-1]].push_back(make_pair(f[j][i-1],j));
		for(int j=0;j<=max(len,n);j++) for(auto v:v1[j]) v2[v.first].push_back(make_pair(j,v.second));
		int cnt=0; pair<int,int> lst=make_pair(-1,-1);
		for(int j=0;j<=max(len,n);j++) for(auto v:v2[j]) cnt+=(make_pair(j,v.first)!=lst),lst=make_pair(j,v.first),f[v.second][i]=cnt;
	}
	for(int i=1;i<=n;i++) ord[i]=f[i][19],rpos[ord[i]]=i;
	vector<pair<int,int>> tmp;
	for(int i=1;i<n;i++) reml[i]=lcp(rpos[i],rpos[i+1]),tmp.push_back(make_pair(reml[i],i));
	sort(tmp.begin(),tmp.end()); reverse(tmp.begin(),tmp.end());
	int it=0,ret=0;
	for(int i=n;i>=1;i--){
		st[i].insert(make_pair(i,a[i])); ret++;
		while(it!=tmp.size()&&tmp[it].first==i){
//			cout<<i<<" "<<tmp[it].first<<" "<<tmp[it].second<<"\n";
			int pos=tmp[it].second;
			int u=find(rpos[pos]),v=find(rpos[pos+1]);
			if(st[u].size()<st[v].size()) swap(u,v);
			ret-=st[u].size(),ret-=st[v].size();
			for(auto p:st[v]){
				vector<pair<int,int>> remdel;
				auto now=st[u].lower_bound(p);
				if(now!=st[u].begin()&&((*prev(now)).second>=p.second)) continue;
				while(now!=st[u].end()&&(p.second>=(*now).second)){
					remdel.push_back(*now);
					now=next(now);
				}
				for(auto q:remdel) st[u].erase(st[u].find(q));
				st[u].insert(p);
			}
			ret+=st[u].size();
			fd[v]=u;
			it++;
		}
		ans[i]=ret;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}