$n$个数的序列,$m + k$种操作
1、$l , r, k$把$l - r$赋值为$k$
2、$l, r, d$询问$l - r$是否有长度为$d$的循环节
首先有个神仙结论:若询问区间为$(l, r, d)$,则只需判断$(l + d, r)$和$(l, r - d )$是否相同
证明可以用归纳法。
然后线段树维护一下字符串hash值,维护一个区间覆盖的标记就好了
注意赋值的时候有$0$的情况,因此开始的标记不能为$0$
#include<cstdio>
#include<algorithm>
#define int long long
#define LL long long
#define ull long long
using namespace std;
const int MAXN = 1e6 + 10;
const double eps = 1e-9;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, K;
char s[MAXN];
struct Segment {
ull sum[MAXN], po[MAXN], seed, mod;
#define ls k << 1
#define rs k << 1 | 1
struct Node {
int l, r, siz;
ull ha, f;
}T[MAXN];
void update(int k) {
T[k].ha = (T[ls].ha % mod + po[T[ls].siz] * T[rs].ha % mod) % mod;
}
void ps(int k, int son) {
T[son].f = T[k].f;
T[son].ha = sum[T[son].siz - 1] * T[son].f % mod;
}
void pushdown(int k) {
if(T[k].f == -1) return ;
ps(k, ls); ps(k, rs);
T[k].f = -1;
}
void Build(int k, int ll, int rr) {
T[k] = (Node) {ll, rr, rr - ll + 1, 0, -1};
if(ll == rr) {
T[k].ha = s[ll] - '0';
return ;
}
int mid = T[k].l + T[k].r >> 1;
Build(ls, ll, mid); Build(rs, mid + 1, rr);
update(k);
}
void IntervalChange(int k, int ll, int rr, ull val) {
if(ll <= T[k].l && T[k].r <= rr) {
T[k].f = val % mod;
T[k].ha = sum[T[k].siz - 1] * val % mod;
return ;
}
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll <= mid) IntervalChange(ls, ll, rr, val);
if(rr > mid) IntervalChange(rs, ll, rr, val);
update(k);
}
ull IntervalQuery(int k, int ll, int rr) {
if(ll > rr) return 0;
if(ll <= T[k].l && T[k].r <= rr) return T[k].ha % mod;
pushdown(k);
int mid = T[k].l + T[k].r >> 1;
if(ll > mid) return IntervalQuery(rs, ll, rr) % mod;
else if(rr <= mid) return IntervalQuery(ls, ll, rr) % mod;
else return (IntervalQuery(ls, ll, rr) % mod + po[mid - max(T[k].l, ll) + 1] * IntervalQuery(rs, ll, rr) % mod) % mod;
}
void work() {
po[0] = 1; sum[0] = 1;
for(int i = 1; i <= N; i++) po[i] = po[i - 1] * seed % mod, sum[i] = (sum[i - 1] + po[i]) % mod;
Build(1, 1, N);
}
int Query(int l, int r, int k) {
return IntervalQuery(1, l, r - k) == IntervalQuery(1, l + k, r);
}
}Se[2];
main() {
Se[0].seed = 27; Se[0].mod = 1e9 + 7;
Se[1].seed = 233; Se[1].mod = 1e9 + 9;
N = read(); M = read(); K = read();
scanf("%s", s + 1);
Se[0].work(); Se[1].work();
for(int i = 1; i <= M + K; i++) {
int opt = read(), l = read(), r = read(), k = read();
if(opt == 1) Se[0].IntervalChange(1, l, r, k), Se[1].IntervalChange(1, l, r, k);
else {
if((r - l + 1) == k) {
puts("YES");
continue;
}
puts((Se[0].Query(l, r, k) && Se[1].Query(l, r, k))? "YES" : "NO");
}
}
return 0;
}