程序地带

Kefa and Watch(字符串哈希线段树)


题目链接:Kefa and Watch
大致题意

给定一个长度为n, 且由数字组成的字符串, 有两种操作:


①把[l, r]区间的数字都变成c


②询问[l, r]区间的数字是否可以 以d为长度作为循环节. (如12345123, 可以以长度为5的12345作为循环节, 只不过最后的123不是完整的循环节)


解题思路

拿到这个题, 很快啊, 我们就发现是一个区间修改和区间询问的问题, 最先想到的就是我们的老朋友线段树.


分析:

对于操作①而言, 只需要维护一个懒标记即可.


对于操作②而言, 我们如何判断一个序列是否可以以长度d作为循环节呢? (由于最后出现的循环节不一定完整, 所以我们不能直接进行判断) 不妨我们这样来想: 假设当前的序列是有长度为d的循环节的, 那么我们假想一个新的序列C, 以[l, l + d]区间的数字为循环节. 我们把当前序列与序列C进行左对齐, 我们发现两个序列共有的部分是完全相同的. 我们如果直接这样创建一个序列, 再去比较, 虽然可以达成要求, 但是单次比较的复杂度会是O(n).


但是我们可以通过上述思路, 把当前序列进行适当的修改, 对齐来达成我们的目的. 前提: 下文中我们称有长度为d的循环节的序列为合法序列.


假设有合法序列X, 如果我把这个序列X的前d个数字直接删除, 那么相较于序列X少了一个循环节, 那么现在新序列(称为序列A)的开头应该是循环节的开头. 我们再把序列X的后面d个数字直接删除, 得到新序列B. 此时序列B也相较于序列X少了一个循环节. 我们此时比较序列A 是否等于 序列B即可.


那么为什么上述方法就可以了呢? 其实你会发现, 在序列A与B比较的过程中, 等价于序列A在与序列C进行比较. 序列X往后搓了一个循环节, 再与自身进行比较. 如果是合法序列, 那么最后一定是完全匹配的.


我们通过上面这些步骤的转换, 我们发现操作②可以通过区间查询的方式进行判断. 对于查询区间[l, r], 是否存在长度为d的循环节, 我们只需要判断 串中[l + d, r]部分与[l, r - d]部分是否完全相同即可. 但是这样下来比较两个字符串的复杂度还是O(n), 但是我们可以采用字符串哈希的方式进行优化. 把字符串比较的复杂度降到常数.


结论:

考察线段树维护字符串哈希. 需要实现区间修改, 区间查询操作.


时间复杂度O(mlogn) 空间复杂度: O(n)


AC代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E5 + 10, mod = 1E9 + 7, B = 13331;
char w[N];
int P[N];
struct node {
int l, r, base;
int hash;
int lazy;
}t[N << 2];
void pushdown(node& op, int lazy) {
op.hash = (ll)lazy * op.base % mod;
op.lazy = lazy;
}
void pushdown(int x) {
if (t[x].lazy == -1) return;
pushdown(t[x << 1], t[x].lazy), pushdown(t[x << 1 | 1], t[x].lazy);
t[x].lazy = -1;
}
void pushup(int x) { t[x].hash = (t[x << 1].hash + t[x << 1 | 1].hash) % mod; }
void build(int l, int r, int x = 1) {
t[x] = { l, r, P[l], (int)(1ll * P[l] * w[l] % mod), -1 };
if (l == r) return;
int mid = l + r >> 1;
build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
t[x].base = (t[x << 1].base + t[x << 1 | 1].base) % mod;
pushup(x);
}
void modify(int l, int r, int c, int x = 1) {
if (l <= t[x].l && r >= t[x].r) {
pushdown(t[x], c);
return;
}
pushdown(x);
int mid = t[x].l + t[x].r >> 1;
if (l <= mid) modify(l, r, c, x << 1);
if (r > mid) modify(l, r, c, x << 1 | 1);
pushup(x);
}
int ask(int l, int r, int x = 1) {
if (l <= t[x].l && r >= t[x].r) return t[x].hash;
pushdown(x);
int mid = t[x].l + t[x].r >> 1;
int res = 0;
if (l <= mid) res += ask(l, r, x << 1);
if (r > mid) res += ask(l, r, x << 1 | 1);
return res % mod;
}
int main()
{
P[0] = 1;
rep(i, N - 5) P[i] = (ll)P[i - 1] * B % mod;
int n, m, q; cin >> n >> m >> q;
scanf("%s", w + 1);
rep(i, n) w[i] -= '0'; //为了和修改操作对应上.
build(1, n);
rep(i, m + q) {
int k, l, r, c; scanf("%d %d %d %d", &k, &l, &r, &c);
if (k == 1) modify(l, r, c);
else {
int res1 = ask(l + c, r), res2 = ask(l, r - c);
res2 = (ll)res2 * P[c] % mod; //对其两个询问的区间
printf("%s ", res1 == res2 ? "YES" : "NO");
}
}
return 0;
}

这个题看网上说也是卡自然取模的, 我之前看一个字符串哈希的题也是QAQ, 所以一般字符串哈希, 还是人工取MOD吧.


END

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45799835/article/details/112689178

随机推荐

python opencv 相机标定_python+opencv相机标定

一、制作标定板将下图打印:图一将打印出的纸固定放到一个平板上,使用同一相机从不同的位置,不同的角度,拍摄标定板的多张照片(10-20张最佳)&#...

weixin_39903538 阅读(783)

python opencv 标定_Python使用OpenCV进行标定

本文结合OpenCV官方样例,对官方样例中的代码进行修改,使其能够正常运行,并对自己采集的数据进行实验和讲解。一、准备OpenCV使用棋盘格板进行标定...

weixin_39600837 阅读(378)