洛谷1117 BZOJ 4650 NOI 2016優秀な分割SA調和級数差分

タイトルリンク
A A AとB B Bは同じである.シリアル長<=30000<=30000<=30000、データ群数<=10<=10<=10.
問題解:95点の暴力があるととっくに聞いていた問題.そして今、正解を発見したのは、特に考えているわけではないでしょう.私はまた問題解で暮らしている.
まず、私たちは1つの列がその形式を満たすかどうかをチェックする必要はありません.私たちは各位置i iに対して、i i iから前にどれだけの形式がA A A AAAAAAの列であるか、後ろにどれだけの長さがA AAAAAAの列であるかを求める必要があります.そして、隣接する位置の前の位置と後ろの位置の後ろの答えを乗じて、この2つの位置を中心とした列の数です.ちょっと拗ねて、式で表すと、x[i]x[i]x[i]x[i]をi i iという位置から前に向かって何個の形式がA A AAAAの列であるか、y[i]y[i]y[i]をi iから後ろに向かって何個の形式がA AAAAの列であるかを表すとすると、Σi=1 n−1 x[i]∗y[i+1]sum_{i=1}^{n-1}x[i]*y[i+1] ∑i=1n−1​x[i]∗y[i+1].
では、次に私たちの問題は、各位置がどれだけ前方と後方の形式がA A AAAAの列であるかをどのように求めるかです.我々のやり方は、A A AAAAの列の中の1つのA A Aの長さl e n lenのように列挙され、その後、l e n lenのように長い間隔でブレークポイントを設定すると、合法的な列A AAAAAAはちょうど2つのブレークポイントをカバーするはずです.では、隣接する2つのブレークポイントについて、統計的な答えを考えます.2つのブレークポイントは、j=i+l e n j=i+len j=i+lenであるi i iおよびj j j jとする.i i iとj j jから前後に最も長い共通接尾辞と最も長い共通接頭辞を求め,i i iから前後に最も長いA A A Aを求め,j j j jから同様に前後にこのようなA A A Aを拡張することができ,つなぎ合わせるとA A AAAAAAとなり,このA A A A Aの長さがl e n len len以上であれば,では、実行可能な答えが出てきました.要求はちょうど2つのブレークポイントを越えるため、この長さはl e n len lenとminを取らなければならない.A A AAAAの起点となる位置が左連続であり、終点となる位置が右連続であることがわかり、もう一つ区間を書くと複雑度が高くなり、最後に検索するだけなので、差分して、左端点+1+1、右端点−1−1−1でよい.その中で最も長い共通接頭辞と最も長い共通接尾辞を求めるときは,まず接尾辞配列+RMQで前処理した.これで私たちは最後に起点と終点の合法的な列にそれぞれ接頭辞をすればいいです.最後に、最初からその乗算式に基づいて答えを求めることができます.
調和級数から分かるように、列挙長さがジャンプするたびにそんなに長い複雑さはO(n l o g n)O(nlogn)O(nlogn)であり、私のところではあまり優秀ではないかもしれませんが、2の乗数と数のlog 2の答えを前に処理すれば、総複素度O(T n l o g n)O(Tnlogn)O(Tnlogn)O(Tnlogn)ができます.複数のグループのクエリは、配列を空にすることを忘れないでください.
コード:

#include 
using namespace std;

int T,sa[30010][2],rk[30010][2],he[30010][18][2],n;
int s[30010],b[30010],c[30010];
long long ans,cnt1[30010],cnt2[30010];
char a[30010];
inline void get_sa(int id)
{
	for(int i=1;i<=n;++i)
	rk[i][id]=a[i];
	memset(s,0,sizeof(s));
	for(int i=1;i<=n;++i)
	s[rk[i][id]]++;
	for(int i=1;i<=255;++i)
	s[i]+=s[i-1];
	for(int i=n;i>=1;--i)
	sa[s[rk[i][id]]--][id]=i;
	int len=1,p=0,x=255;
	while(p<n)
	{
		int k=0;
		for(int i=n-len+1;i<=n;++i)
		b[++k]=i;
		for(int i=1;i<=n;++i)
		{
			if(sa[i][id]>len)
			b[++k]=sa[i][id]-len;
		}
		for(int i=1;i<=n;++i)
		c[i]=rk[b[i]][id];
		memset(s,0,sizeof(s));
		for(int i=1;i<=n;++i)
		s[c[i]]++;
		for(int i=1;i<=x;++i)
		s[i]+=s[i-1];
		for(int i=n;i>=1;--i)
		sa[s[c[i]]--][id]=b[i];
		for(int i=1;i<=n;++i)
		c[i]=rk[i][id];
		p=1;
		rk[sa[1][id]][id]=1;
		for(int i=2;i<=n;++i)
		{
			if(!(c[sa[i][id]]==c[sa[i-1][id]]&&c[sa[i][id]+len]==c[sa[i-1][id]+len]))
			++p;
			rk[sa[i][id]][id]=p;
		}
		len*=2;
		x=p;
	}
	x=0;
	for(int i=1;i<=n;++i)
	{
		if(rk[i][id]==1)
		continue;
		if(x)
		--x;
		int j=sa[rk[i][id]-1][id];
		while(a[i+x]==a[j+x])
		++x;
		he[rk[i][id]][0][id]=x;
	}
	for(int j=1;(1<<j)<=n;++j)
	{
		for(int i=1;i<=n-(1<<j)+1;++i)
		he[i][j][id]=min(he[i][j-1][id],he[i+(1<<(j-1))][j-1][id]);
	}
}
inline int lcp(int x,int y,int id)
{
	if(x>y)
	swap(x,y);
	int z=log2(y-x);
	return min(he[x+1][z][id],he[y-(1<<z)+1][z][id]);
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		ans=0;
		memset(cnt1,0,sizeof(cnt1));
		memset(cnt2,0,sizeof(cnt2));
		memset(a,0,sizeof(a));
		memset(sa,0,sizeof(sa));
		memset(he,0,sizeof(he));
		memset(rk,0,sizeof(rk));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		scanf("%s",a+1);
		n=strlen(a+1);		
		get_sa(0);
		reverse(a+1,a+n+1);
		get_sa(1);		
		for(int len=1;len<=n/2;++len)
		{
			for(int i=len,j=len<<1;j<=n;i+=len,j+=len)
			{
				int x=min(lcp(rk[i][0],rk[j][0],0),len),y=min(lcp(rk[n-(i-1)+1][1],rk[n-(j-1)+1][1],1),len-1);
				int ji=x+y-len+1;
				if(x+y>=len)
				{
					cnt1[i-y]++;
					cnt1[i-y+ji]--;
					cnt2[j+x-ji]++;
					cnt2[j+x]--;
				}
			}
		}
		for(int i=1;i<=n;++i)
		{
			cnt1[i]+=cnt1[i-1];
			cnt2[i]+=cnt2[i-1];
		}
		for(int i=1;i<=n-1;++i)
		ans+=cnt2[i]*cnt1[i+1];
		printf("%lld
",ans);
	}
	return 0;
}