$Link$
有一个小写字母串 $S$。
有 $n$ 种操作，每种操作可以执行任意次。第 $i$ 种操作是将区间 $[l_i,r_i]$ 的字母变为它在字母表中的后继（$z$ 的后继为 $a$）。
问能否可以通过这些操作将 $S$ 变为一个回文串。
$1\le|S|,n\le10^5$。
首先把 $S$ 转成一个值域为 $[1,26]$，自带取模的数字串，操作就相当于一个区间加。
套路性地，我们把序列（这里我们在头尾加个 $0$）做一个差分，那么一个回文串等价于就是所有对称的位置的差分值都互为相反数。
一个区间加的操作，相当于在差分序列上打一个 $+1$ 和 $-1$ 的操作，也就是调整的机会。于是我们只要满足这四个值加起来等于 $0$ 就好了。
那我们只要在对称位置连边，有操作的位置连边，合法的情况当且仅当联通块的和为 $0$。
时间复杂度 $O((n+|S|)\alpha)$。
$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
| #include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
int f = 1, x = 0;
char ch;
do{
ch = getchar();
if (ch == '-')
f = -1;
}while(ch < '0' || ch > '9');
do{
x = x * 10 + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return f * x;
}
const int N = 1e5;
int n, m;
string s;
int a[N + 2], sum[N + 2];
int fa[N + 2], sz[N + 2];
inline int gfa(int x)
{
if (fa[x] != x)
fa[x] = gfa(fa[x]);
return fa[x];
}
inline void merge(int x, int y)
{
x = gfa(x);
y = gfa(y);
if (x == y)
return;
if (sz[x] < sz[y])
swap(x, y);
fa[y] = x;
sz[x] += sz[y];
return;
}
int main()
{
cin >> s;
n = s.size();
for (int i = 0; i < n; i++)
a[i + 1] = s[i] - 'a' + 1;
for (int i = n + 1; i >= 1; i--) {
a[i] -= a[i - 1];
fa[i] = i;
sz[i] = 1;
}
m = read();
for (int i = 1; i <= m; i++) {
int l = read(), r = read();
merge(l, r + 1);
}
for (int i = 1, j = n + 1; i < j; i++, j--)
merge(i, j);
for (int i = 1; i <= n + 1; i++)
sum[gfa(i)] += a[i];
for (int i = 1; i <= n + 1; i++) {
if (gfa(i) == i && sum[i] % 26) {
printf("NO\n");
return 0;
}
}
printf("YES\n");
return 0;
}
|