Lijinrui299792458

不做沉底的木做举重若轻的船。

CF700E Cool Slogans

发表于 更新于

题目描述

Link

简意：定义字符串等级为出现在其中至少两次的最高等级的子串的等级 +1，空串等级为 0，求给定字符串的等级。

思路

首先，看到子串的问题，可以想到 SAM。然而任意子串的子串似乎还是不太好表示。在 SAM 上，我们通过边来连接前缀，用 fa 连接后缀。SAM 将子串转化为前缀和后缀。那么类似地，我们对于某一个子串，先继承它前缀的答案，然后用它的后缀，即 Parent Tree 上的祖先来更新。

在进一步的讨论之前，我们先来讨论一个问题：SAM 上一个节点表示了多个串，我们更新答案时肯定等级越大越好，所以我们存一个节点中最长子串的等级。然而这会不会影响“至少出现两次”？最长的子串没有出现两次，有没有可能有更短的子串出现两次？

我们期望它没有影响。现在来尝试证明它：

如果一个短串（非此节点中最长串）在一个串中两次出现，现在将这个短串向前拓展一位 endpos 一定不变，即任何一个位置上拓展都是可行的。那么如果这是长串的末尾，长串也一定可以拓展出去。

那么我们只需维护每一个节点上最长串的等级。

当我们计算一个节点的等级时，它一定不小于其前缀节点答案最大值。而我们再看它至少出现两次的后缀中等级的最大值，最后取最大值即可。

首先，一个串的等级一定不会比它的后缀小。那么我只需知道，在这个节点的祖先中，保持着其等级在祖先中最大的后缀中最短的那一个是否出现两次即可，很好维护。

那么我们怎么判断是否出现两次呢？

我们发现，一个节点的 endpos 可以通过它儿子的 endpos 之并得到。而我们需要查询的就是一个节点的 endpos 在一个区间中是否出现，那么可以用线段树合并。然而我们是在 Parent Tree 上从下往上求的，而更新的顺序大概上是逆着这个顺序的（不是严格的）。那么还需可持久化一下。

最后，我们按什么顺序更新？为了方便处理，我直接按照了 Maxl 递增的顺序，这样一定是前更新后。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair

	struct Sam
	{
		int ml,fa,ch[26],et,fp;
	}s[400005];int cnt=1,lst=1;
	void ad(int c)
	{
		int x=lst;lst=++cnt;s[cnt].ml=s[x].ml+1,s[cnt].et=s[x].et+1;
		while(x&&(!s[x].ch[c]))s[x].ch[c]=cnt,x=s[x].fa;
		if(!x)
		{
			s[lst].fa=1;
			return;
		}
		int y=s[x].ch[c];
		if(s[x].ml+1==s[y].ml)
		{
			s[lst].fa=y;
			return;
		}
		s[++cnt]=s[y],s[cnt].et=0,s[cnt].ml=s[x].ml+1,s[cnt].fa=s[y].fa,s[y].fa=s[lst].fa=cnt;
		while(x&&s[x].ch[c]==y)s[x].ch[c]=cnt,x=s[x].fa;
	}

int len;
vector <int> son[400005];
int p[400005];
int rt[400005];
struct segmenttree
{
	int ls,rs,sum;
}t[20000005];int siz;

void upd(int x)
{
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}

int merge(int u,int v)
{
	if(!u)
	{
		return v;
	}
	if(!v)
	{
		return u;
	}
	int now=++siz;
	t[now].ls=merge(t[u].ls,t[v].ls),t[now].rs=merge(t[u].rs,t[v].rs);
	upd(now);
	return now;
}
void insert(int &_,int l,int r,int v)
{
	if(!_)_=++siz;
	if(l==r)return (void)(t[_].sum=1);
	int mid=l+r>>1;
	if(v<=mid)insert(t[_].ls,l,mid,v);
	else insert(t[_].rs,mid+1,r,v);
	upd(_);
}
int build(int x)
{
	rt[x]=0;
	s[x].fp=len;
	for(int i:son[x])
	rt[x]=merge(build(i),rt[x]),
	s[x].fp=min(s[x].fp,s[i].fp);
	if(s[x].et)
	{
		s[x].fp=min(s[x].fp,s[x].et);
		insert(rt[x],1,len,s[x].et);
	}
	return rt[x];
}
int query(int x,int l,int r,int L,int R)
{
	if(r<L||l>R)return 0;
	if(L<=l&&R>=r)return t[x].sum;
	int mid=l+r>>1;
	return query(t[x].ls,l,mid,L,R)+
	query(t[x].rs,mid+1,r,L,R);
}

bool cmp(int x,int y)
{
	return s[x].ml<s[y].ml;
}

int ans[400005],up[400005];

int main()
{
	char c;
	scanf("%d",&len);
    while((c=getchar())<'a'||c>'z');
	while((c)>='a'&&c<='z')ad(c-'a'),c=getchar();
	p[1]=1;
	for(int i=2;i<=cnt;i++)son[s[i].fa].push_back(i),p[i]=i;
	build(1);
	sort(p+2,p+1+cnt,cmp);
	for(int i=2;i<=cnt;i++)
	{
		if(ans[p[i]]>ans[s[p[i]].fa])
		{
			up[p[i]]=p[i];
			for(int j=0;j<26;j++)if(s[p[i]].ch[j])ans[s[p[i]].ch[j]]=max(ans[s[p[i]].ch[j]],ans[p[i]]);
			continue;
		}
		if(s[p[i]].fa==1)
		{
			ans[p[i]]=1,up[p[i]]=p[i];
			for(int j=0;j<26;j++)if(s[p[i]].ch[j])ans[s[p[i]].ch[j]]=max(ans[s[p[i]].ch[j]],ans[p[i]]);
			continue;
		}
		if(query(rt[up[s[p[i]].fa]],1,len,s[p[i]].fp-s[p[i]].ml+s[up[s[p[i]].fa]].ml,s[p[i]].fp-1))
		{
			up[p[i]]=p[i],ans[p[i]]=ans[s[p[i]].fa]+1;
			for(int j=0;j<26;j++)if(s[p[i]].ch[j])ans[s[p[i]].ch[j]]=max(ans[s[p[i]].ch[j]],ans[p[i]]);
			continue;
		}
		up[p[i]]=up[s[p[i]].fa],ans[p[i]]=ans[s[p[i]].fa];
		for(int j=0;j<26;j++)if(s[p[i]].ch[j])ans[s[p[i]].ch[j]]=max(ans[s[p[i]].ch[j]],ans[p[i]]);
	}
	printf("%d",ans[p[cnt]]);
	return 0;
}