Alice and Bod
Alice 和 Bob 正在玩一个最近兴起的游戏，名为死亡对称，一人进攻一人防守，进攻方可以进攻 m 次，m 次后如果防守成功则防守方获胜，否则进攻方获胜。
Alice 防守，Bob 进攻。 具体规则如下，给定一个长度为 n 的字符串，进攻方 Bob 每次可以进行如下两种操作的一种。
1 l r 向 Alice 询问一段字符串的子串 $s[l,r]$ 是否是对称的，即要求 $s_{l+i}=s_{r−i}(0 \leq i \leq r−l)$。
2 l r x 将给定字符串的子串 $s[l,r]$ 一段的每个字符同时变成它在字典序中后面的第 $x (0 \leq x \leq 10^9)$ 个字符，并且规定 $z$ 在字典序中后面的第 $1$ 个字符为 $a$。
Alice 很想赢得这个游戏，但是他对于字符串一窍不通，希望得到你的帮助，在每次询问时做出正确的答案。
输入描述:
第一行输入两个整数 $n(1 \leq n \leq 10^5)$，$m(1 \leq m \leq 10^5)$ 分别表示字符串的长度和进攻次数。
第二行输入一个长度为 $n$ 的字符串 $s$，保证全部由小写字母构成。 接下来输入 $m$ 行，每行表示一个操作。
输出描述:
对于每次 Bob 的第一种进攻，若是对称的则输出 YES ，否则输出 NO。
示例1
输入
3 5
aaz
1 1 3
2 3 3 1
1 1 2
2 1 3 1
1 1 3输出
NO
YES
YES说明
第一次操作时，字符串为 $aaz$ ，子串 $s[1...3]$，为 $aaz$，并不对称，输出 NO。
第二次操作，字符串变为 $aaa$ 第三次操作时，字符串为 $aaa$，子串 $s[1...2]$ 为 $aa$，对称，输出 YES。
第四次操作，字符串变为 $bbb$ 第五次操作，字符串为 $bbb$，子串 $s[1...3]$，为 $bbb$，是对称的，输出 YES。
解题思路
要判断子串 $s_l \ldots s_r$ 是不是回文串，一种 $O(1)$ 的判断方法是判断 $h(s_l \ldots s_r)$ 是否等于 $h(s_r \ldots s_l)$，其中 $h(s)$ 是字符串 $s$ 的哈希值。因此我们可以用线段树去维护每个区间对应的正反子串的哈希值。具体的，对于维护区间 $[l,r]$ 的线段树节点，维护正子串 $s_l \ldots s_r$ 的哈希值 $h_1 = s_{l} \cdot P^{r-l} + s_{l+1} \cdot P^{r-l-1} + \cdots + s_{r} \cdot P^{0}$，维护反子串 $s_r \ldots s_l$ 的哈希值 $h_2 = s_{l} \cdot P^{0} + s_{l+1} \cdot P^{1} + \cdots + s_{r} \cdot P^{r-l}$。假设要与另外一个字符串 $s'$ 拼接，那么拼接后的字符串的哈希值分别是 $h_1 \cdot P^{|s'|} + h_1'$，$h_2 + h_2' \cdot P^{|s|}$，这对应 pushup 操作。
以 $h_1$ 为例，对于修改操作，需要将其更新为
$$((s_{l} + x) \bmod 26) \cdot P^{r-l} + ((s_{l+1} + x) \bmod 26) \cdot P^{r-l-1} + \cdots + ((s_{r} + x) \bmod 26) \cdot P^{0}$$
可以发现很难仅通过原本的 $h1$ 去更新成这个值。对于修改操作，本质上是将每种字符都循环右移 $x$ 位。
举个具体的例子，有 $s = caazca$，$x = 2$，原本的 $h_1 = c \cdot P^{5} + a \cdot P^{4} + a \cdot P^{3} + z \cdot P^{2} + c \cdot P^{1} + a \cdot P^{0}$。修改后字符串变成 $s' = eccbec$，对应的 $h_1' = e \cdot P^{5} + c \cdot P^{4} + c \cdot P^{3} + b \cdot P^{2} + e \cdot P^{1} + c \cdot P^{0}$。可以发现，原本的 $a \cdot P^{4} + a \cdot P^{3} + a \cdot P^{0}$ 变成 $c \cdot P^{4} + c \cdot P^{3} + c \cdot P^{0}$；原本的 $c \cdot P^{5} + c \cdot P^{1}$ 变成 $e \cdot P^{5} + e \cdot P^{1}$；原本的 $z \cdot P^{2}$ 变成 $b \cdot P^{2}$。
这启发我们可以开个大小为 $26$ 的数组来存储每个字符对应的多项式，修改的时候只需对该数组循环右移 $x$ 个单位，就可以得到每种字符变化后得到的多项式，而 $h_1$ 则可以通过对各个字符乘以其多项式求和得到。对 $h_2$ 的维护同理。更多的细节可以参考代码。
自然溢出取模的 AC 代码如下，时间复杂度为 $O(26 \, m \log{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 5, P = 13331;
char s[N];
ULL p[N];
struct Node {
int l, r, len, add;
array<ULL, 26> h1, h2;
}tr[N * 4];
void pushup(Node &u, Node l, Node r) {
u.len = l.len + r.len;
for (int i = 0; i < 26; i++) {
u.h1[i] = l.h1[i] * p[r.len] + r.h1[i];
u.h2[i] = l.h2[i] + r.h2[i] * p[l.len];
}
}
void build(int u, int l, int r) {
tr[u] = {l, r, r - l + 1};
if (l == r) {
int t = s[l] - 'a';
tr[u].h1[t] = tr[u].h2[t] = 1;
}
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
}
void upd(int u, int c) {
rotate(tr[u].h1.begin(), tr[u].h1.end() - c, tr[u].h1.end());
rotate(tr[u].h2.begin(), tr[u].h2.end() - c, tr[u].h2.end());
tr[u].add = (tr[u].add + c) % 26;
}
void pushdown(int u) {
if (tr[u].add) {
upd(u << 1, tr[u].add);
upd(u << 1 | 1, tr[u].add);
tr[u].add = 0;
}
}
void modify(int u, int l, int r, int c) {
if (tr[u].l >= l && tr[u].r <= r) {
upd(u, c);
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, c);
if (r >= mid + 1) modify(u << 1 | 1, l, r, c);
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
}
Node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
if (l >= mid + 1) return query(u << 1 | 1, l, r);
Node t;
pushup(t, query(u << 1, l, r), query(u << 1 | 1, l, r));
return t;
}
int main() {
int n, m;
cin >> n >> m >> s;
memmove(s + 1, s, n + 1);
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P;
}
build(1, 1, n);
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
Node t = query(1, l, r);
ULL h = 0;
for (int i = 0; i < 26; i++) {
h += (t.h1[i] - t.h2[i]) * (i + 1);
}
cout << (h ? "NO" : "YES") << '\n';
}
else {
int c;
cin >> c;
modify(1, l, r, c % 26);
}
}
return 0;
}随机模数的 AC 代码如下，时间复杂度为 $O(26 \, m \log{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5;
const LL P = uniform_int_distribution<int> (131, 13331)(rng), mod = uniform_int_distribution<int> (1e9, 2e9)(rng);
char s[N];
LL p[N];
struct Node {
int l, r, len, add;
array<int, 26> h1, h2;
}tr[N * 4];
void pushup(Node &u, Node l, Node r) {
u.len = l.len + r.len;
for (int i = 0; i < 26; i++) {
u.h1[i] = (l.h1[i] * p[r.len] + r.h1[i]) % mod;
u.h2[i] = (l.h2[i] + r.h2[i] * p[l.len]) % mod;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r, r - l + 1};
if (l == r) {
int t = s[l] - 'a';
tr[u].h1[t] = tr[u].h2[t] = 1;
}
else {
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
}
void upd(int u, int c) {
rotate(tr[u].h1.begin(), tr[u].h1.end() - c, tr[u].h1.end());
rotate(tr[u].h2.begin(), tr[u].h2.end() - c, tr[u].h2.end());
tr[u].add = (tr[u].add + c) % 26;
}
void pushdown(int u) {
if (tr[u].add) {
upd(u << 1, tr[u].add);
upd(u << 1 | 1, tr[u].add);
tr[u].add = 0;
}
}
void modify(int u, int l, int r, int c) {
if (tr[u].l >= l && tr[u].r <= r) {
upd(u, c);
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, c);
if (r >= mid + 1) modify(u << 1 | 1, l, r, c);
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
}
Node query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
if (l >= mid + 1) return query(u << 1 | 1, l, r);
Node t;
pushup(t, query(u << 1, l, r), query(u << 1 | 1, l, r));
return t;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m >> s;
memmove(s + 1, s, n + 1);
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P % mod;
}
build(1, 1, n);
while (m--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
Node t = query(1, l, r);
int h = 0;
for (int i = 0; i < 26; i++) {
h = (h + (t.h1[i] - t.h2[i]) * (i + 1ll)) % mod;
}
cout << (h ? "NO" : "YES") << '\n';
}
else {
int c;
cin >> c;
modify(1, l, r, c % 26);
}
}
return 0;
}
参考资料
题解 | #练习赛129题解#：https://blog.nowcoder.net/n/dab6e8baab16457da0e5ac1c72da2d9d
标签：26,cdot,h1,tr,Alice,len,int,Bod From： https://www.cnblogs.com/onlyblues/p/18440933