「CF700E」 Cool Slogans - 后缀自动机 + 线段树合并 + 贪心

给出一个长度为$n$的字符串$s_1$，由小写字母组成

定义一个字符串序列$s_{1 \sim k}$，满足性质：$s_i$在$s_{i-1} (i\ge2)$中出现至少两次（位置可重叠）

求最大的$k$是多少，使得从$s_1$开始到$s_k$都满足这样一个性质

$n\le 2\times 10^5$

Links

CF 700E

Solution

倒着考虑，考虑每次多选出来一个子串使得它包含了当前子串至少两次

注意到一个性质，假设我们已经选出了$i-1$个串，那么一定存在一种最优方案使得第$i$个串的右端点与第$i-1$个串的右端点相同

假设存在一个方案使得右端点不同，那么肯定可以通过割掉当前这个串右边的那一段多余部分使得它们的右端点相同，且这样割掉只会使得后面的转移更优

那么选出来的就是一些右端点相同的后缀（本来这里是想贴几张图的，结果写题解的时候机房网烂了，就算了。。。）

发现这个东西实际上就是SAM中parent树上的一条链，于是可以在parent树上贪心地选：只要当前状态能使得答案更优就选它，否则继承父亲的状态

设$f[i]$表示SAM上从根到节点$i$最多能选出来的子串数，$g[i]$表示这个最优方案最后一个选的状态是什么

在parent树上贪心，对于一个节点$x$每次判断一下$g[fa[x]]$的right集合中是否存在两个位置$p$满足$pos[x] - maxlen[x] + 1\le p - minlen[g[fa[x]] + 1$且

其中$pos[x]$表示状态$x$的right集合中任意一个右端点的位置，线段树合并维护一下right集合即可，这个小技巧和「NOI2018」你的名字差不多

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAX_N = 200000 + 100;

int N;
char S[MAX_N];

namespace SEG
{
#define mid (l + r >> 1)
#define ls node[root].ch[0]
#define rs node[root].ch[1]
#define lson ls, l, mid
#define rson rs, mid + 1, r

	const int MAX_NODE = MAX_N * 40;

	int node_cnt;

	struct info
	{
		int cnt, ch[2];
	} node[MAX_NODE];

	inline void push_up (int root) { node[root].cnt = node[ls].cnt + node[rs].cnt; }

	inline void insert (int &root, int l, int r, int x)
	{
		++node[root = ++node_cnt].cnt;
		if (l == r) return ;
		if (x <= mid) insert (lson, x);
		else insert (rson, x);
	}

	inline int merge (int x, int y, int l, int r)
	{
		if (!x || !y) return x | y;
		int root = ++node_cnt;
		ls = merge (node[x].ch[0], node[y].ch[0], l, mid);
		rs = merge (node[x].ch[1], node[y].ch[1], mid + 1, r);
		push_up (root);
		return root;
	}

	inline int query (int root, int l, int r, int x, int y)
	{
		if (x > y) return 0;
		if (x <= l && r <= y) return node[root].cnt;

		int ans = 0;
		if (x <= mid) ans += query (lson, x, y);
		if (y > mid) ans += query (rson, x, y);
		return ans;
	}

#undef mid 
#undef ls 
#undef rs 
#undef lson
#undef rson
}

namespace SAM
{
	const int MAX_NODE  = MAX_N << 1;

	int node_cnt, last;
	int Root[MAX_NODE];

	struct info
	{
		int ch[27], maxlen, fa, pos;
	} node[MAX_NODE];

	vector <int> G[MAX_NODE];

	int f[MAX_NODE], g[MAX_NODE]; // f : 最大值, g : 最大值产生的状态
	int State[MAX_NODE];

	inline int new_node (int pre)
	{
		node[++node_cnt].maxlen = node[pre].maxlen + 1;
		return node_cnt;
	}

	inline int extend (int c, int pos)
	{
		int now = new_node (last), pre = last; last = now;
		node[now].pos = pos;
		
		for (; pre && !node[pre].ch[c]; pre = node[pre].fa) node[pre].ch[c] = now;

		if (!pre) node[now].fa = 1;
		else
		{
			int x = node[pre].ch[c];
			if (node[x].maxlen == node[pre].maxlen + 1) node[now].fa = x;
			else
			{
				int y = ++node_cnt;
				node[y] = node[x], node[y].maxlen = node[pre].maxlen + 1;
				node[x].fa = node[now].fa = y;

				for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;
			}
		}

		return now;
	}

	inline void build (char *s, int n)
	{
		node_cnt = last = 1;
		for (int i = 1; i <= n; ++i) State[i] = extend (s[i] - 'a', i);
		for (int i = 1; i <= n; ++i) SEG :: insert (Root[State[i]], 1, node_cnt, i);
	}

	inline void dfs (int x)
	{
		for (int i = 0; i < G[x].size(); ++i)
		{
			int y = G[x][i];
			dfs (y);
			Root[x] = SEG :: merge (Root[x], Root[y], 1, N);
		}
	}

	int ans = 0;

	inline void dfs_calc (int x)
	{
		Chkmax(ans, f[x]);
		for (int i = 0; i < G[x].size(); ++i)
		{
			int y = G[x][i];

			if (x == 1) f[y] = 1, g[y] = y; 
			else if (SEG :: query (Root[g[x]], 1, node_cnt, node[y].pos + node[node[g[x]].fa].maxlen + 1 - node[y].maxlen, node[y].pos) >= 2) f[y] = f[x] + 1, g[y] = y;
			else f[y] = f[x], g[y] = g[x];

			dfs_calc (y);
		}
	}

	inline void solve ()
	{
		for (int i = 1; i <= node_cnt; ++i) G[node[i].fa].pb (i);
		dfs (1), dfs_calc (1);
		cout << ans << endl;
	}
}

inline void Solve ()
{
	SAM :: build (S, N);
	SAM :: solve ();
}

inline void Input ()
{
	N = read<int>();
	scanf("%s", S + 1);
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}