At提交记录

#include <iostream>
typedef long long ll;
using namespace std;

const ll MAXN = 1e6, p1 = 131, m1 = 1e9 + 7, p2 = 137, m2 = 998244353, p3 = 139, m3 = 1e9 - 63, p4 = 149, m4 = 1e9 + 9;

ll n, q, pw1[MAXN + 5] = {1}, pw2[MAXN + 5] = {1}, pw3[MAXN + 5] = {1}, pw4[MAXN + 5] = {1};
string s, r;

ll lb(ll x) {
	return x & -x;
}
struct BIT1 {
	ll size, val[MAXN + 5] = {};
	void add(ll x, ll v) {
//		cout << "add " << x << " " << v << endl;
		ll pos = x;
		while (pos <= size) {
			val[pos] += v * pw1[pos - x] % m1;
			val[pos] %= m1;
			pos += lb(pos);
		}
	}
	ll qry(ll x) {
		ll pos = x, ret = 0;
		while (pos) {
			ret += val[pos] * pw1[x - pos] % m1;
			ret %= m1;
			pos -= lb(pos);
		}
		return ret % m1;
	}
	ll qry(ll l, ll r) {
		if (l > r) {
			return qry(r, l);
		}
		return (qry(r) - qry(l - 1) * pw1[r - l + 1] % m1 + m1) % m1;
	}
} s1, r1;
struct BIT2 {
	ll size, val[MAXN + 5] = {};
	void add(ll x, ll v) {
		ll pos = x;
		while (pos <= size) {
			val[pos] += v * pw2[pos - x] % m2;
			val[pos] %= m2;
			pos += lb(pos);
		}
	}
	ll qry(ll x) {
		ll pos = x, ret = 0;
		while (pos) {
			ret += val[pos] * pw2[x - pos] % m2;
			ret %= m2;
			pos -= lb(pos);
		}
		return ret % m2;
	}
	ll qry(ll l, ll r) {
		if (l > r) {
			return qry(r, l);
		}
		return (qry(r) - qry(l - 1) * pw2[r - l + 1] % m2 + m2) % m2;
	}
} s2, r2;
struct BIT3 {
	ll size, val[MAXN + 5] = {};
	void add(ll x, ll v) {
		ll pos = x;
		while (pos <= size) {
			val[pos] += v * pw3[pos - x] % m3;
			val[pos] %= m3;
			pos += lb(pos);
		}
	}
	ll qry(ll x) {
		ll pos = x, ret = 0;
		while (pos) {
			ret += val[pos] * pw3[x - pos] % m3;
			ret %= m3;
			pos -= lb(pos);
		}
		return ret % m3;
	}
	ll qry(ll l, ll r) {
		if (l > r) {
			return qry(r, l);
		}
		return (qry(r) - qry(l - 1) * pw3[r - l + 1] % m3 + m3) % m3;
	}
} s3, r3;
struct BIT4 {
	ll size, val[MAXN + 5] = {};
	void add(ll x, ll v) {
		ll pos = x;
		while (pos <= size) {
			val[pos] += v * pw4[pos - x] % m4;
			val[pos] %= m4;
			pos += lb(pos);
		}
	}
	ll qry(ll x) {
		ll pos = x, ret = 0;
		while (pos) {
			ret += val[pos] * pw4[x - pos] % m4;
			ret %= m4;
			pos -= lb(pos);
		}
		return ret % m4;
	}
	ll qry(ll l, ll r) {
		if (l > r) {
			return qry(r, l);
		}
		return (qry(r) - qry(l - 1) * pw4[r - l + 1] % m4 + m4) % m4;
	}
} s4, r4;

int main() {
	cin >> n >> q >> s;
	s1.size = r1.size = s2.size = r2.size = s3.size = r3.size = s4.size = r4.size = n;
//	for (ll i = 1; i <= n; i++) {
//		r[i - 1] = s[n - i];
//	}
	for (ll i = 1; i <= n; i++) {
		pw1[i] = pw1[i - 1] * p1 % m1;
		pw2[i] = pw2[i - 1] * p2 % m2;
		pw3[i] = pw3[i - 1] * p3 % m3;
		pw4[i] = pw4[i - 1] * p4 % m4;
	}
	for (ll i = 1; i <= n; i++) {
		s1.add(i, s[i - 1]);
		r1.add(n - i + 1, s[i - 1]);
		s2.add(i, s[i - 1]);
		r2.add(n - i + 1, s[i - 1]);
		s3.add(i, s[i - 1]);
		r3.add(n - i + 1, s[i - 1]);
		s4.add(i, s[i - 1]);
		r4.add(n - i + 1, s[i - 1]);
	}
//	for (ll i = 1; i <= n; i++) {
//		cout << s1.val[i] << " ";
//	}
//	cout << endl;
	while (q--) {
		ll o;
		cin >> o;
		if (o == 1) {
			ll x;
			char c;
			cin >> x >> c;
			s1.add(x, c - s[x - 1]);
			r1.add(n - x + 1, c - s[x - 1]);
			s2.add(x, c - s[x - 1]);
			r2.add(n - x + 1, c - s[x - 1]);
			s3.add(x, c - s[x - 1]);
			r3.add(n - x + 1, c - s[x - 1]);
			s4.add(x, c - s[x - 1]);
			r4.add(n - x + 1, c - s[x - 1]);
			s[x - 1] = c;
		} else if (o == 2) {
			ll l, r;
			cin >> l >> r;
			if (s1.qry(l, r) == r1.qry(n - r + 1, n - l + 1) && s2.qry(l, r) == r2.qry(n - r + 1, n - l + 1) && s3.qry(l, r) == r3.qry(n - r + 1, n - l + 1) && s4.qry(l, r) == r4.qry(n - r + 1, n - l + 1)) {
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
//			cout << s1.qry(l, r) << " " << r1.qry(n - r + 1, n - l + 1) << endl;
		}
	}
	return 0;
}