luogu P5161 WD与数列 SAM 线段树合并启发式合并

LINK：WD与数列

这道题可谓妙绝我明白了一个增量统计的原理。

原本的想法是：差分之后显然长度为1的单独统计长度为2的以及更多就是字符串之间的匹配问题了。

对差分序列建立SAM 由于第一个是一定匹配的且后面的大小关系相同所以可以直接取差分后的来建立SAM.

考虑计算答案容易想到对于某个节点单独统计答案那就是right集合上len暴力扫了可能可以通过45分我没试过且这个暴力过于暴力也不好说明复杂度.

考虑一件事情其实统计答案的本质是 len.right集合中x,y三者之间造成的贡献。

单独考虑两个x,y 此时没必要强制考虑当前节点的len 因为在之后他们一定会把1~lenmx 都统计一遍所以在两个right集第一次相遇时就可以把之后的答案给得到.

所以这个暴力的改进是每次对于新加入的right集合直接对已有的right集合计算贡献且贡献的区间长度为1~len.

两个endpos之间产生贡献最坏复杂度就是n^2的了.

这个就叫做增量统计贡献.

对于新加入的x统计之前所有的y的贡献这个东西可以利用线段树来快速统计大体上就是判断lenmx的有多少不是的话就利用|x-y|-1类似的东西统计。

这样就是logn快速统计一个决策的答案了。

不过这个决策的数量每次在合并的时候并没有保证最坏还是n^2logn的。

考虑每次是两个决策集合合并的过程利用启发式合并就可以保证每个决策最多被合并logn次了。

这样总复杂度nlog^2.非常的妙。

值得一提的是出题人的初衷是让我们写SA 利用容斥和优秀的拆分那道题的方法来统计答案这样也很妙这样可以做到nlogn.

不过这种方法细节较多没有线段树来的暴力 (理解优秀的拆分的方法就行辣

const int MAXN=300010<<1;

int n,last=1,id,cnt=1;ll ans,sum1,sum2;

int a[MAXN],f[MAXN],len[MAXN],c[MAXN],q[MAXN],w[MAXN],root[MAXN];

map<int,int>t[MAXN];vector<int>g[MAXN];

struct wy{int l,r;ll sum;int cnt;}s[MAXN*40];

inline void insert(int &p,int l,int r,int x)

{

	if(!p)p=++id;

	if(l==r){++c(p);sum(p)+=x;return;}

	int mid=(l+r)>>1;

	if(x<=mid)insert(l(p),l,mid,x);

	else insert(r(p),mid+1,r,x);

	sum(p)=sum(l(p))+sum(r(p));

	c(p)=c(l(p))+c(r(p));

}

inline void insert(int x,int ww)

{

	int p=last;

	int np=last=++cnt;w[last]=last;

	len[np]=len[p]+1;g[last].pb(ww);

	insert(root[last],1,n-1,ww);

	while(p&&!t[p][x])

	{

		t[p][x]=np;

		p=f[p];

	}

	if(!p)f[np]=1;

	else

	{

		int q=t[p][x];

		if(len[q]==len[p]+1)f[np]=q;

		else

		{

			int nq=++cnt;

			t[nq]=t[q];f[nq]=f[q];

			len[nq]=len[p]+1;

			f[q]=f[np]=nq;

			while(p&&t[p][x]==q)

			{

				t[p][x]=nq;

				p=f[p];

			}

		}

	}

}

inline void topsort()

{

	rep(1,cnt,i)++c[len[i]];

	rep(1,cnt,i)c[i]+=c[i-1];

	rep(1,cnt,i)q[c[len[i]]--]=i;

}

inline int ask(int p,int l,int r,int L,int R)

{

	if(!p||L>n-1||R<1||L>R)return 0;

	if(L<=l&&R>=r)return c(p);

	int mid=(l+r)>>1,cnt=0;

	if(L<=mid)cnt+=ask(l(p),l,mid,L,R);

	if(R>mid)cnt+=ask(r(p),mid+1,r,L,R);

	return cnt;

}

inline void ask1(int p,int l,int r,int L,int R)

{

	if(!p||L>n-1||R<1||L>R)return;

	if(!p)return;

	if(L<=l&&R>=r){sum1+=c(p);sum2+=sum(p);return;}

	int mid=(l+r)>>1;

	if(L<=mid)ask1(l(p),l,mid,L,R);

	if(R>mid)ask1(r(p),mid+1,r,L,R);

}

inline int merge(int x,int y,int l,int r)

{

	if(!x||!y)return x|y;

	if(l==r){c(x)+=c(y);sum(x)+=sum(y);return x;}

	int mid=(l+r)>>1;

	l(x)=merge(l(x),l(y),l,mid);

	r(x)=merge(r(x),r(y),mid+1,r);

	sum(x)=sum(l(x))+sum(r(x));

	c(x)=c(l(x))+c(r(x));

	return x;

}

int main()

{

	//freopen("1.in","r",stdin);

	get(n);get(a[1]);

	rep(2,n,i)get(a[i]),insert(a[i]-a[i-1],i-1);

	topsort();

	fep(cnt,2,i)

	{

		int x=q[i],fa=f[x];

		if(fa==1)continue;

		if(g[w[fa]].size()<g[w[x]].size())

		{

			swap(w[fa],w[x]);

			swap(root[fa],root[x]);

		}

		//启发式合并保证复杂度正确.

		for(ui int j=0;j<g[w[x]].size();++j)

		{

			int tn=g[w[x]][j];

			ans+=(ll)ask(root[fa],1,n-1,tn+len[fa]+1,n-1)*len[fa];

			ans+=(ll)ask(root[fa],1,n-1,1,tn-len[fa]-1)*len[fa];

			sum1=sum2=0;ask1(root[fa],1,n-1,tn+1,tn+len[fa]);

			ans+=sum2-sum1*tn-sum1;

			sum1=sum2=0;ask1(root[fa],1,n-1,tn-len[fa],tn-1);

			ans+=sum1*tn-sum2-sum1;

			g[w[fa]].pb(tn);

		}

		root[fa]=merge(root[fa],root[x],1,n-1);

	}

	ans+=(ll)n*(n-1)/2;putl(ans);

	return 0;

}

巴特西

luogu P5161 WD与数列 SAM 线段树合并启发式合并

最新文章

热门文章

巴特西

luogu P5161 WD与数列 SAM 线段树合并 启发式合并

最新文章

热门文章

luogu P5161 WD与数列 SAM 线段树合并启发式合并