Codeforces 700E. Cool Slogans(SAM+DP+可持久化线段树合并)

题解

  这场比赛质量好高高啊,题题都很好玩玩
  首先很容易可以发现一些性质。a1a_1一定只有一个字母。假设当前串为结束在位置RR长度为lenlen的串,每次一定是找到最大的LRL\neq R满足S[Llen+1:L]=S[Rlen+1:R]S[L-len+1:L]=S[R-len+1:R],然后把当前串变为S[Llen+1:R]S[L-len+1:R]
  可以发现上面所需要的操作是可以用SAM做到的。
  具体做法就是对于一个状态里的一个串,一定是每次找rightright集合里相邻的两个rr拼成一个字符串,然后转移到儿子节点中深度最小的lenlen\geq这个新串长度的状态,其实就是DP,但是这样复杂度显然无法承受。我们知道DP刷表法是无法优化的,但是查表法可以,所以我们反过来考虑一个状态从祖先状态转移。因为每次转移题目中的kk只会+1,所以显然优化就是记录前缀最大值,即记录xx到根的最大的kk
  还有一个性质,那么就是对于一个状态xx中长度小的串能够转移到下一个状态,那么显然长度大的串也能够转移到下一个状态yy,并且kk不会更劣,因为他们的rightright集合是一样的,并且状态yylenlen也足够长到能满足新串中xx的最长串出现两次,否则状态yylenlen一定可以再增长一些。
  那么设posxpos_x为状态xxkk最大的祖先,转移的条件是,对于xxrightright集合中的任意一个rrposxpos_xrightright集合中必定存在一个r[rlen[x]+len[posx],r1]r' \in [r-len[x]+len[pos_x],r-1],也就是状态xxlenlen足够长到能表示新串。
  那么就用可持久化线段树合并来维护每一个节点的rightright集合即可。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9;
struct sgt{int lt, rt;}tree[maxn*20];
struct sam{int len, fa, trans[26];}st[maxn<<1];
int n, sgttot, root, now, tott, ans;
int f[maxn], pos[maxn], rgt[maxn], troot[maxn], cnt[maxn], rk[maxn];
char s[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

bool query(int x, int l, int r, int cl, int cr)
{
	if(!x) return 0;
	if(cl<=l && r<=cr) return 1;
	int mid=(l+r)>>1;
	if(cl<=mid && query(tree[x].lt, l, mid, cl, cr)) return 1; 
	if(cr>mid && query(tree[x].rt, mid+1, r, cl, cr)) return 1; 
	return 0;
}

int merge(int x, int y)
{
	if(!x || !y) return x+y;
	int nx=++sgttot;
	tree[nx].lt=merge(tree[x].lt, tree[y].lt);
	tree[nx].rt=merge(tree[x].rt, tree[y].rt);
	return nx;
}

void update(int &x, int l, int r, int cx)
{
	if(!x) x=++sgttot;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(cx<=mid) update(tree[x].lt, l, mid, cx);
	else update(tree[x].rt, mid+1, r, cx);
}

inline void extend(int ch, int x)
{
	int np=++tott, p=now;
	st[np].len=st[p].len+1; now=np; rgt[np]=x;
	while(p && !st[p].trans[ch]) st[p].trans[ch]=np, p=st[p].fa;
	if(!p) st[np].fa=root;
	else
	{
		int q=st[p].trans[ch];
		if(st[p].len+1==st[q].len) st[np].fa=q;
		else
		{
			int nq=++tott; rgt[nq]=x;
			st[nq]=st[q];
			st[nq].len=st[p].len+1;
			st[np].fa=st[q].fa=nq;
			while(p && st[p].trans[ch]==q) st[p].trans[ch]=nq, p=st[p].fa;
		}
	}
}

inline void prepare()
{
	for(int i=1;i<=tott;i++) cnt[st[i].len]++;
	for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
	for(int i=tott;i;i--) rk[cnt[st[i].len]--]=i;
	for(int i=tott;i>=2;i--)
	{
		int x=rk[i];
		update(troot[x], 1, n, rgt[x]);
		troot[st[x].fa]=merge(troot[st[x].fa], troot[x]);
	}
}
 
int main()
{
	read(n); scanf("%s", s+1); root=now=tott=1;
	for(int i=1;i<=n;i++) extend(s[i]-'a', i);
	prepare();
	for(int i=2;i<=tott;i++)
	{
		int x=rk[i], fa=pos[st[x].fa];
		if(st[x].fa==root) f[x]=1, pos[x]=x;
		else if(query(troot[fa], 1, n, rgt[x]-st[x].len+st[fa].len, rgt[x]-1)) f[x]=f[fa]+1, pos[x]=x;
		else f[x]=f[fa], pos[x]=pos[fa];
		ans=max(ans, f[x]);
	}
	printf("%d\n", ans);
}