区间推平，区间查询循环节

区间推平，区间查询循环节

题意

给定一个字符串 \(s\) , 请你支持两种操作：

\(1, l, r, c\)：将 \([l,r]\) 之间的字符改为 \(c\)。

\(2, l, r, d\)：询问 \([l,r]\) 之间是否有长度为 \(d\) 的循环节，有输出 YES，否则输出 NO。

思路

使用线段树维护区间哈希值，区间推平使用等比数列计算。

区间 \([l,r]\) 有长度为 \(d\) 的循环节当且仅当 \([l,r-d]=[l+d,r]\)，使用哈希判断。

时间复杂度：\(O(n+q\log n)\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 5;
using LL = long long;

const LL mod = 1e9 + 7;
const LL base = 17;

LL pw[N];
LL inv_base;

LL qpow(LL x, LL y, LL p) {
	LL res = 1;
	for (; y; y >>= 1, x = x * x % p)
		if (y & 1) res = res * x % p;
	return res;
}

LL inv(LL x, LL p) {
	return qpow(x, p - 2, p);
}

struct segt {
	struct node {
		int l, r, cov;
		LL hash;
		node() {
			l = r = 0;
			cov = -1;
			hash = 0;
		}
	} t[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
	friend node operator + (node x, node y) {
		node res;
		res.l = x.l, res.r = y.r;
		res.hash = (x.hash * pw[y.r - y.l + 1] % mod + y.hash) % mod;
		res.cov = -1;
		return res;
	}
	void build(int p, int l, int r, char *s) {
		t[p].l = l, t[p].r = r;
		t[p].cov = -1;
		if (l == r) {
			t[p].hash = s[l] - '0';
			return ;
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid, s);
		build(rs, mid + 1, r, s);
		t[p] = t[ls] + t[rs];
	}
	
	void make_cov(int p, int v) {
		t[p].hash = v * (pw[t[p].r - t[p].l + 1] - 1) % mod * inv_base % mod;
		t[p].hash = (t[p].hash % mod + mod) % mod;
		t[p].cov = v;
	}
	
	void push_down(int p) {
		if (~t[p].cov) {
			make_cov(ls, t[p].cov);
			make_cov(rs, t[p].cov);
			t[p].cov = -1;
		}
	}
	
	void cov(int p, int l, int r, int c) {
		if (l <= t[p].l && t[p].r <= r) {
			make_cov(p, c);
			return ;
		}
		push_down(p);
		if (l <= t[ls].r) cov(ls, l, r, c);
		if (r >= t[rs].l) cov(rs, l, r, c);
		t[p] = t[ls] + t[rs];
	}
	
	node query(int p, int l, int r) {
		if (l > r) return node();
		if (l <= t[p].l && t[p].r <= r) return t[p];
		push_down(p);
		if (r <= t[ls].r) return query(ls, l, r); 		
		if (l >= t[rs].l) return query(rs, l, r);
		return query(ls, l, r) + query(rs, l, r);
	}
} T;

int n, m;
char s[N];

void init() {
	pw[0] = 1;
	for (int i = 1; i <= 1e6 + 2; i ++) 
		pw[i] = pw[i - 1] * base % mod;
	inv_base = inv(base - 1, mod);
	T.build(1, 1, n, s);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	cin >> (s + 1);
	init();
	while (m --) {
		int op, l, r, d, c;
		cin >> op >> l >> r;
		if (op == 1) {
			cin >> c;
			T.cov(1, l, r, c);
		}
		if (op == 2) {
			cin >> d;
			auto res1 = T.query(1, l, r - d);
			auto res2 = T.query(1, l + d, r);
			if (res1.hash == res2.hash) return cout << "YES\n", 1;
			else cout << "NO\n";
		}
	}
	return 1;
}