前言

"I'm free."

做法与题解区都不同，虽然麻烦，但是毕竟复杂度是对的，而且想法很自然，还是写一写吧！

Solution

题意：给定长为 \(n\) 的字符串 \(s\) 和长为 \(n\) 的数组 \(A\)，对于每个 \(r\)，求 满足 \(\text{LCP}(\text{Suffix}(x),\text{Suffix}(y))\ge r,x<y\) 的数对 \((x,y)\) 数量。

其中 \(\text{LCP}(x,y)\) 指字符串 \(x,y\) 的最长公共前缀，\(\text{Suffix}(i)\) 表示串 \(s\) 从第 \(i\) 位开始的后缀。

然后记数对 \((x,y)\) 权值为 \(A_x\times A_y\)，对于每个 \(r\)，求满足上述条件的数对的最大权值。

一、串串题惯常套路

看见要求原串两个后缀的 \(\text{LCP}\)，最直接的反应便是启动后缀数组，并计算出 \(height\) 数组。

然后 \(\text{LCP}(\text{Suffix}(x),\text{Suffix}(y))=\min_{i\in [rank_x+1,rank_y]} h_i,rank_x<rank_y\) 便可求出任意两个后缀的 \(\text{LCP}\)。

现在我们就把字符串问题转移为数列问题。

二、具体解决方案

现在相当于询问对于每个 \(r\)，有多少满足 \(\min_{i\in [x+1,y]}h_i \ge r,x<y\) 的数对 \((x,y)\)。

此时出现三个考虑方向：

第一是分别计算每一位 \(h_i\) 对答案贡献。

第二是从大到小枚举 \(r\) ，使用并查集维护区间的阻断或者连通性，计算答案是多少。

但是其实正序计算也是可以哒！

我们把 \(h_i\) 从小到大排序，并一个一个按原位置加入数组中。

容易发现，加入所有 \(h_i<i\) 之后，仍然不包含任何数字的区间，就是对于 \(r=i\) 时的一个合法区间。

举个例子：

\(\min_{i\in [2,4]}=1\)，意味着 \(\text{LCP}(\text{Suffix}(sa_{2-1}),\text{Suffix}(sa_4))=1\)，事实的确如此。

对于一个连续的空区间，任选其中两点（左端点可以选到左边的数字上），皆是一个合法答案，设其长度为 \(l\)，对第一问贡献为 \(l\times (l+1)\div 2\)。

考虑在数组中加入一个数，会对答案产生什么样的影响？

会把一个连续空区间分成两个。

那么对于第一问是简单的，减去原来长区间贡献，分别加入两个短区间贡献即可。

三、第二问咋做

仍然考虑一个长区间对于整体的贡献。

上文已经提到，对于一个连续的空区间，任选其中两点（左端点可以选到左边的数字上），皆是一个合法答案。

为了使得权值最大化，显然要选 \(A_i\) 最大的两个，或者最小的两个（负负得正）。

这是一个典型的询问区间最大和次大，使用数据结构维护即可。

然后对于区间的贡献，不仅有删除和添加（把一个大区间分成两个后，删除大区间贡献，加入两个小区间贡献），还要实时查询各个区间贡献的最大值，还是用数据结构来维护。

四、实现细节

用啥数据结构呢？

询问区间最大次大和最小次小，由于不带修，ST 表即可。

（但是我倍增不熟，赛时怕挂，便使用了线段树来维护）

如何找到左右最靠近的加入过的数，单调栈或者树状数组或者 set 都可以。

（这里建议最后一个，但是我赛时使用了最麻烦的第二个）

如何实时查询贡献最大值并支持加入删除某个数？堆或者 multiset。

时间复杂度都是 \(\text{O}(n\log n)\)，但是一个 \(\log\) 遍地跑，常数贼大。

（实测最慢点 \(970\) 到 \(1500\) 毫秒不等，通过率高于 \(50\%\)）。

这个做法最大的区别便是正序枚举 \(r\)，并使用堆来解决第二问。

贴一个修改过的赛时代码，很唐。

趣事：赛时没有使用 multiset 而用的 set，但是过了所有测试数据，洛谷上被官方数据搞成 \(70\) 了。

"Save me."

AC Code

#include<bits/stdc++.h>
#define int long long
#define For(l,r,b) for(b=l;b<=r;b++)
#define N 300005
#define inf 1000000007ll
using namespace std;
string s;
int i,j,sa[N],rk[N],rk1[N],sec[N],tot[N],n,h[N];
int tr[N][2];
int a[N],A[N];
vector<int> hp[N];
struct tree{
	int l,r,s1,s2,b1,b2;
}t[4*N];
struct an{
	int s1,s2,b1,b2;
};
an mi(an x,an y)
{
	return {min(x.s1,y.s1),min(max(x.s1,y.s1),min(x.s2,y.s2)),max(x.b1,y.b1),max(min(x.b1,y.b1),max(x.b2,y.b2))};
}
void pushup(int o)
{
	an x={t[o*2].s1,t[o*2].s2,t[o*2].b1,t[o*2].b2},y={t[o*2+1].s1,t[o*2+1].s2,t[o*2+1].b1,t[o*2+1].b2};
	an xy=mi(x,y);
	t[o]={t[o].l,t[o].r,xy.s1,xy.s2,xy.b1,xy.b2};
}
multiset<int> se;
multiset<int>::iterator it;
void build(int l,int r,int o)
{
	t[o].l=l;t[o].r=r;
	if(l==r)
	{
		t[o].s1=t[o].b1=A[l];
		t[o].s2=inf;
		t[o].b2=-inf;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,o*2);
	build(mid+1,r,o*2+1);
	pushup(o);
}
an query(int l,int r,int o)
{
	if(t[o].l>=l&&t[o].r<=r) return {t[o].s1,t[o].s2,t[o].b1,t[o].b2};
	int mid=(t[o].l+t[o].r)>>1;
	an ans={inf,inf,-inf,-inf};
	if(l<=mid) ans=mi(ans,query(l,r,o*2));
	if(r>mid) ans=mi(ans,query(l,r,o*2+1));
	return ans;
}
void change(int x,int y,int id)
{
	x++;
	for(;x<=n;x+=x&-x) tr[x][id]=max(tr[x][id],y);
}
int ask(int x,int id)
{
	x++;
	int ans=-1;
	for(;x>0;x-=x&-x) ans=max(ans,tr[x][id]);
	return ans;
}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0); 
	cin>>n>>s;
	For(1,n,i) cin>>a[i];
	s='#'+s;
	For(1,n,i) tot[s[i]]++,rk[i]=s[i];
	For(1,128,i) tot[i]+=tot[i-1];
	for(i=n;i;i--) sa[tot[rk[i]]--]=i;
	int sz=128;
	for(int k=1;k<=n;k<<=1)
	{
		int cnt=0;
		For(n-k+1,n,i) sec[++cnt]=i;
		For(1,n,i) if(sa[i]>k) sec[++cnt]=sa[i]-k;
		memset(tot+1,0,sz<<3);
		For(1,n,i) ++tot[rk[i]];
		For(1,sz,i) tot[i]+=tot[i-1];
		for(i=n;i>=1;i--) sa[tot[rk[sec[i]]]--]=sec[i];
		memcpy(rk1+1,rk+1,n<<3);
		sz=1;
		rk[sa[1]]=1;
		For(2,n,i) rk[sa[i]]=(rk1[sa[i]]==rk1[sa[i-1]]&&rk1[sa[i]+k]==rk1[sa[i-1]+k])?sz:++sz;
		if(sz==n) break;
	}
	For(1,n,i)
	{
		int pt=max(0ll,h[rk[i-1]]-1);
		while(s[i+pt]==s[sa[rk[i]-1]+pt]) pt++;
		h[rk[i]]=pt;
	}
	h[1]=0;
	For(1,n,i) A[i]=a[sa[i]];
	For(1,n,i) hp[h[i]].push_back(i);
	build(1,n,1);
	an as=query(1,n,1);
	change(1,1,0);change(0,0,1);
	long long ans=(n-1)*n/2,an2=max(as.b1*as.b2,as.s1*as.s2);
	cout<<ans<<" "<<an2<<endl;
	For(0,n-2,i)
	{
		for(auto j:hp[i])
		{
			int lf=ask(j-1,0),rf=n+1-ask(n-j,1);
			if(j==1) lf++;
			lf++,rf--;
			an gx;int gp;
			if(rf>=lf)
			{
				gx=query(lf-1,rf,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
				it=se.lower_bound(-gp);
				if(gp!=inf*inf&&j!=1)se.erase(se.lower_bound(-gp));
			}
			ans-=(rf-lf+1)*(rf-lf+2)/2;
			ans+=(j+1-lf)*(j-lf)/2;
			ans+=(rf-j+1)*(rf-j)/2;
			if(j-1>=lf)
			{
				gx=query(lf-1,j-1,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
				if(gp!=inf*inf) se.insert(-gp);
			}
			if(j+1<=rf)
			{
				gx=query(j,rf,1),gp=max(gx.b1*gx.b2,gx.s1*gx.s2);
				if(gp!=inf*inf) se.insert(-gp);
			}
			change(j,j,0);change(n+1-j,n+1-j,1);
		}
		cout<<ans<<" "<<(ans==0?0:(-(*se.lower_bound(-inf*inf))))<<endl;
	}
	return 0;
}

后记

写得比较认真的一篇题解。

谨以此题解，为我长达四天的字符串简单学习作结，也为基本 OI 知识的第一轮学习作结。

"I won't leave you."