CF356E – Xenia and String Problem – 题解

CodeForces CF356E – Xenia and String Problem

这是一种不需要任何数据结构和处理字符串的工具，但细节繁多的做法。

设全串为 $s_{1\dots n}$。不难发现，Gray string 的串长必然是 $2^w-1\quad (w\geq 1)$ 的形式。若其长为 $2^w-1$，我们称其为 $w-1$ 阶 Gray string。

同时用归纳法可以证明，设一个 $w$ 阶 Gray string 的起始位置为 $x+1$（其终到位置为 $x+2^{w+1}$），那么必然有 $$\forall k\in\{0,1,\cdots,w\},s_{x+2^k}=s_{x+2^k+2^{k+1}}=s_{x+2^k+2\times 2^{k+1}}=\cdots=s_{x+2^k+(2^{w-k}-1)2^{k+1}}\\ \forall i,j,0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j}$$ 成立。例如一个 $3$ 阶 Gray string 可以被描述为 $\mathtt{abacabadabacaba}$。

考虑在不更改字符的情况下，计算所有位置 $x\quad (0\leq x<n)$ 有多少 $w$ 满足 $s_{x+1\dots x+2^{w+1}}$ 是 Gray string。我们记 $g(y,w)$ 为最大的 $k$，满足 $s_y=s_{y+2^{w+1}}=s_{y+2\times 2^{w+1}}=\cdots=s_{y+(k-1)2^{w+1}}$，也即间隔为 $2^{w+1}$ 的极长邻项字符相等的链。这可以暴力 $\newcommand\bigO{\operatorname{O}}\bigO(n\log n)$ 求出。那么位置 $x$ 能够贡献一个 $w$ 阶 Gray string，当且仅当 $$\forall 0\leq i\leq w,w\leq i+\lfloor\log_2 g(x+2^i,i)\rfloor\\ \forall 0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j}$$ 这依然可以 $\bigO(n\log n)$ 求出——我们从小到大遍历 $w$ 并更新上文式子的最小值，直到 $w$ 超过这个最小值或者出现重复字符。固定位置 $x$，记 $w_0$ 是满足上式的最大 $w$。

现在思考当某个位置的字符被替换后，$x$ 的贡献有何变化。我们分两个部分考虑：删除和新增。记在全串范围内，将 $s_u$ 变为字符 $c$ 会新增 $h(u,c)$ 的权值和。

被删除的串

易得对于所有 $u\quad (x<u<x+2^{w+1})$，$s_u$ 的改变将直接破坏 Gray string $s_{x+1\dots x+2^{w+1}-1}$；特别地，若 $u=x+2^w$（该 Gray string 的中央字符），且有 $\forall 0\leq i<w, {s_u}’\neq s_{x+2^i}$（不与更低阶的字符重复），则这个 $w$ 阶 Gray string 不会被破坏。

于是我们设立差分数组 $d(x)\quad(1\leq x\leq n)$，维护破坏造成的负权值。记 $b_w=(2^{w+1}-1)^2$。令 $$\begin{aligned} {d(x+1)}’&\leftarrow d(x+1)-b_w\\ {d(x+2^{w+1})}’&\leftarrow d(x+2^{w+1})+b_w\\ {d(x+2^w)}’&\leftarrow d(x+2^w)+b_w\\ {d(x+2^w+1)}’&\leftarrow d(x+2^w+1)-b_w&\text{（中央字符可以改变）}\\ \forall i,0\leq i<w,{h(x+2^w,s_{x+2^i})}’&\leftarrow h(x+2^w,s_{x+2^i})-(2^{w+1}-1)^2&（但不能改为重复字符） \end{aligned}$$

新增的串

我们称位置 $x$ 的扩展被阻拦，当且仅当有 $\forall 0\leq w\leq w_0,w_0<w+\lfloor\log_2 g(x+2^w,w)\rfloor$。这也就意味着 $w_o+1$ 阶位置出现了重复字符；反之，未被阻拦是说 $w_0$ 恰等于了限制式的上界。按照这个定义，同时出现 $w_0$ 卡到上界和 $w_0+1$ 阶位置有重复字符的话，会被归为“未阻拦”。

未被阻拦

我们令 $j$ 是所有 $w\quad (0\leq w\leq w_0)$ 中取到 $w_0=w+\lfloor\log_2 g(x+2^w,w)\rfloor$ 的值，也即上界的来源。若 $j$ 不唯一，由于替换单个字符最多更改一个 $g(x+2^w,w)$，故而 $w_0$ 不会改变，不可能在 $x$ 处有新的贡献。

若 $j$ 唯一，有两种可能使得 $g(x+2^j,j)$ 变大。记应用 ${g(x+2^j,j)}’$ 得到的新上界为 ${w_0}’$。

• $u=x+2^j+2^{j+1}g(x+2^j,j)$ 且 ${s_u}’=s_{x+2^j}$，也即 $u$ 为 $j$ 阶链尾的下一个位置。将 $s_u$ 设置为 $s_{x+2^j}$，就是将它合并到 $j$ 阶极长链上——这甚至还可能导致 $u$ 两侧两条 $j$ 阶链的合并；
• $j=w_0$ 且 $u_2=u=x+2^j$ 且 $\forall 0\leq w\leq w_0, {s_u}’\neq s_{x+2^w}$。由 $j=w_0$ 可以推出 $\lfloor\log_2 g(x+2^j,j)\rfloor=0\iff g(x+2^j,j)=1$，也即这条链长为 $1$。此时将该位置本身替换成 $s_{u+2^{j+1}}$（如果其与低阶的链不重复），可能会引发两条链的合并，较原串更优。

不难说明，其他任何位置替换任何字符，都只会使得 $x$ 的贡献削减（$g(x+2^w,w)$ 不增）；而负贡献已经在上文中计算完成了。如果上文两种情况有新的贡献，则我们分别累加 $h(u,{s_u}’)’\leftarrow h(u,{s_u}’)+\sum_{w=w_0+1}^{{w_0}’} b_w$。

被阻拦

可以验证，被阻拦时只有改变 $s_{u=x+2^{w_0+1}}$，也即 $w_0+1$ 阶链的首字符，才有可能在 $x$ 处有新贡献。若有 ${s_u}’\neq s_{x+2^{w_0+1}x+2^{w_0+2}}$（试图合并两条 $w_0+1$ 阶链），可能有 ${w_0}’>w_0+1$；否则必然有 ${g(u,w_0+1)}’=1,{w_0}’=w_0+1$。只有一种情况需要重新暴力计算。及时更新 $h(u,*)$ 即可。

最后我们从前到后累加差分，利用 $h$ 更新答案即可。

按照上述方法精细实现，可以做到 $\bigO(n\log n)$，常数小。是为目前本题最优解。

Submission #187976651

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
#include <bits/stdc++.h>
using namespace std;

#define inl __attribute__((always_inline)) inline
typedef long long ll;
typedef pair <int, int> pint;
#define fst first
#define scd second
#define all(p) begin (p), end (p)
#define empb emplace_back

constexpr int N = 1e5 + 10;
constexpr ll b[] = { 1, 9, 49, 225, 961, 3969, 16129, 65025, 261121, 1046529,
	4190209, 16769025, 67092481, 268402689, 1073676289, 4294836225, 17179607041 };
constexpr ll bpre[] = { 1, 10, 59, 284, 1245, 5214, 21343, 86368, 347489, 1394018,
	5584227, 22353252, 89445733, 357848422, 1431524711, 5726360936, 22905967977 };
int n, g[17][N]; char s[N]; ll ans, dt[N], ata[N][26];

inl int cnxt (int x, int i) { return x + g[i][x+(1<<i)] * (1<<i+1) + (1<<i); }
inl int ced (int x, int i) { return x + g[i][x+(1<<i)] * (1<<i+1) - (1<<i); }
inl int cst (int x, int i) { return x + (1<<i); }
inl int imple (int x) {
	static bool occ[26];
	int w = 0, lmt = INT_MAX, y;
	memset (occ, 0, 26);
	while (w <= lmt && !occ[s[y = cst (x, w)]-'a'])
		lmt = min (lmt, __lg (g[w][y]) + w),
		occ[s[y] - 'a'] = 1, ++w;
	return --w;
}

int main () {
	/*  */
	scanf ("%s", s + 1); n = strlen (s + 1);
	for (int w = 0; (1<<w) <= n; ++w)
		for (int st = 1; st <= 1<<w+1; ++st) {
			int x = st, y = st, cnt = 0;
			while (x <= n) {
				while (y <= n && s[x] == s[y]) y += 1<<w+1, ++cnt;
				while (x < y) g[w][x] = cnt--, x += 1<<w+1;
			}
		}

	for (int x = 0; x < n; ++x) {
		static bool occ[26];
		static int bd[17], lst[17];
		memset (occ, 0, 26);
		int w = 0, lmt = INT_MAX, y, z, c, _g, alp;
		while (w <= lmt && !occ[s[y = cst (x, w)]-'a'])
			lmt = min (lmt, bd[w] = __lg (g[w][y]) + w),
			occ[lst[w++] = s[y] - 'a'] = 1;
		
		ans += bpre[--w], dt[x + 1] -= bpre[w];
		for (int i = 0; i <= w; ++i) {
			dt[x+(1<<i+1)] += b[i],
			dt[y = cst (x, i)] += b[i], dt[y+1] -= b[i];
			for (int k = 0; k < i; ++k)
				ata[y][lst[k]] -= b[i];
		}

		if (w == lmt) {
			// ? 无阻拦/非严格阻拦。
			int j = -1;
			for (int i = 0; i <= w; ++i)
				if (bd[i] == w) j = ~j ? INT_MAX : i;
			if (j == INT_MAX) continue;
			// ? 在j阶后面补足。
			if ((z = cnxt (x, j)) > n) goto KAWA;
			c = s[z], s[z] = s[y = cst (x, j)];
			_g = g[j][y], g[j][y] += 1 + ((alp = z + (1<<j+1)) <= n
				&& s[alp] == s[y] ? g[j][alp] : 0);
			ata[z][s[y]-'a'] += bpre[imple (x)] - bpre[w];
			g[j][y] = _g, s[z] = c;
			// ? 若有j = w，则自然有j阶连通块大小为1。尝试改换它自己的颜色。
			KAWA: if (j != w || (z = cnxt (x, w)) > n
				|| occ[s[z] - 'a']) continue;
			c = s[y = cst (x, w)], s[y] = s[z];
			_g = g[w][y], g[w][y] += g[w][z];
			ata[y][s[z]-'a'] += bpre[imple (x)] - bpre[w];
			g[w][y] = _g, s[y] = c;
		} else {
			// ? 严格阻拦。
			// ? 添置一个没有出现过的字符。
			for (c = 0, y = cst (x, w+1); c < 26; ++c)
				ata[y][c] += !occ[c] * b[w+1];
			if (g[w+1][y] > 1 || (z = y + (1<<w+2)) > n) continue;
			ata[y][s[z]-'a'] -= b[w+1];
			c = s[y], s[y] = s[z], g[w+1][y] += g[w+1][z];
			ata[y][s[z]-'a'] += bpre[imple (x)] - bpre[w];
			s[y] = c, g[w+1][y] = 1;
		}
	}

	for (ll ima = ans, x = 1; x <= n; ++x)
		ans = max (ans, (ima += dt[x]) + *max_element (all (ata[x])));
	printf ("%lld", ans);

	return 0;
}