题目描述
小红拿到了一个字符串,她将进行以下两种操作:
$- 1 \quad x \quad c$:将第$x$个字符修改为$c$
$- 2 \quad l_1 \quad r_1 \quad l_2 \quad r_2$:查询$s[l1,r1]$子串是否和$s[l2,r2]$子串相等。
输入描述:
第一行输入两个正整数$n,q$,用空格隔开。代表字符串初始长度和询问次数。
第二行输入一个长度为$n$的、仅由小写字母组成的字符串。
接下来的$q$行,每行输入一行操作。操作的形式如输入描述所示。$1≤n≤10^6 , 1≤q≤10^5 , 1≤l_1≤r_1≤n , 1≤l_2≤r_2≤n , r_1−l_1=r_2−l_2 , 1≤x≤n$ , $c$保证是小写字母。
输出描述:
对于每个操作 $2$,如果两子串相等,则输出$Yes$。否则输出$No$
示例1
输入
5 4
abcba
2 1 2 4 5
1 3 a
2 1 3 3 5
2 1 3 2 4
输出
No
Yes
No
题目分析
线段树+字符串哈希
根据题目,我们将字符串哈希过后就可以看作对数组进行修改和查询操作了,基础线段树(单点修改+区间查询)
字符串哈希有两种方式
第一种是自然溢出,靠unsigned long long
对$2^{64}$的自然取模
第二种是取双模
有个值得注意的点,为了防止区间查询的结果很大,很难将两端区间分别基数化
将原本的判断条件
query(1, l1, r1) / p[l1] == query(1, l2, r2) / p[l2]
改为
query(1, l1, r1) == query(1, l2, r2) * p[u] || query(1, l1, r1) * p[u] == query(1, l2, r2)
亲测,改之前是爆WA , 0分
代码
1.自然溢出
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 1000010, P = 131;
int n, q;
char s[N];
int h[N], p[N];
struct Node
{
int l, r;
int v, sum;
} tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
if (l == r)
tr[u] = {l, r, h[l], h[l]};
else
{
int mid = l + r >> 1;
tr[u] = {l, r};
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
int query(int u, int l, int r)
{
int res = 0;
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
res += query(u << 1, l, r);
if (r > mid)
res += query(u << 1 | 1, l, r);
return res;
}
void modify(int u, int x, char c)
{
if (tr[u].l == x && tr[u].r == x)
{
tr[u].v = tr[u].sum = c * p[x];
s[x] = c;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid)
modify(u << 1, x, c);
else
modify(u << 1 | 1, x, c);
pushup(u);
}
}
signed main()
{
cin >> n >> q;
cin >> s + 1;
p[0] = 1;
for (int i = 1; i <= n; i++)
{
p[i] = p[i - 1] * P;
h[i] = s[i] * p[i];
}
build(1, 1, n);
int op;
while (q--)
{
cin >> op;
if (op == 1)
{
char c;
int x;
cin >> x >> c;
modify(1, x, c);
}
else if (op == 2)
{
signed l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int u = abs(l1 - l2);
if (query(1, l1, r1) == query(1, l2, r2) * p[u] || query(1, l1, r1) * p[u] == query(1, l2, r2))
puts("Yes");
else
puts("No");
}
}
}
2.双模哈希
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010, MOD_1 = 1e9 + 7, MOD_2 = 1e9 + 9;
typedef pair<int, int> PII;
const PII P = {13331, 23333};
int n, q;
char s[N];
PII h[N], p[N];
PII operator+(PII a, PII b)
{
int c1 = a.first + b.first, c2 = a.second + b.second;
if (c1 >= MOD_1)
c1 -= MOD_1;
if (c2 >= MOD_2)
c2 -= MOD_2;
return {c1, c2};
}
PII operator-(PII a, PII b)
{
int c1 = a.first - b.first, c2 = a.second - b.second;
if (c1 < 0)
c1 += MOD_1;
if (c2 < 0)
c2 += MOD_2;
return {c1, c2};
}
PII operator*(PII a, PII b)
{
return {a.first * b.first % MOD_1, a.second * b.second % MOD_2};
}
struct Node
{
int l, r;
PII v, sum;
} tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
if (l == r)
tr[u] = {l, r, h[l], h[l]};
else
{
int mid = l + r >> 1;
tr[u] = {l, r};
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
PII query(int u, int l, int r)
{
PII res = {0, 0};
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
res = res + query(u << 1, l, r);
if (r > mid)
res = res + query(u << 1 | 1, l, r);
return res;
}
void modify(int u, int x, char c)
{
if (tr[u].l == x && tr[u].r == x)
{
tr[u].v = tr[u].sum = make_pair(c, c) * p[x];
s[x] = c;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid)
modify(u << 1, x, c);
else
modify(u << 1 | 1, x, c);
pushup(u);
}
}
signed main()
{
cin >> n >> q;
cin >> s + 1;
p[0] = {1, 1};
for (int i = 1; i <= n; i++)
{
p[i] = p[i - 1] * P;
h[i] = make_pair(s[i], s[i]) * p[i];
}
build(1, 1, n);
int op;
while (q--)
{
cin >> op;
if (op == 1)
{
char c;
int x;
cin >> x >> c;
modify(1, x, c);
}
else if (op == 2)
{
signed l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int u = abs(l1 - l2);
if (query(1, l1, r1) == query(1, l2, r2) * p[u] || query(1, l1, r1) * p[u] == query(1, l2, r2))
puts("Yes");
else
puts("No");
}
}
}