QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1020#657810#9302. Caesar Ciphership2077ACAAASuccess!2024-10-21 09:31:162024-10-21 09:31:17

Details

Extra Test:

Wrong Answer
time: 1ms
memory: 9772kb

input:

40 1
0 0 9 0 12 25 2 0 0 0 0 0 0 0 0 0 24 0 0 1 1 0 0 24 0 0 0 0 0 0 0 0 0 2 25 12 0 9 0 0
2 1 21 20

output:

yes

result:

wrong answer expected NO, found YES [1st token]

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#657810#9302. Caesar CipherACAAA#WA 979ms68220kbC++232.5kb2024-10-19 15:30:212024-10-21 09:31:48

answer

#include <algorithm>
#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int base = 13331;
const int mod = 1e9 + 7,p= 65535;
typedef long long ll;
int n, m, a[N],p1[N],p2[N];
struct Node {
	int l, r;
	ll val,maxn,len,tag;
}tr[N<<2];
void pushup(Node& t, Node& lc, Node& rc) {
	t.val = (rc.val + lc.val * p1[rc.len] % mod) % mod;
	t.maxn = max(lc.maxn, rc.maxn);
	t.len = lc.len + rc.len;
}
void pushup(int k) {
	pushup(tr[k], tr[k << 1], tr[k << 1 | 1]);
}
void pushdown(Node& t, Node& lc, Node& rc) {
	lc.val = (lc.val + t.tag * p2[lc.len-1] % mod) % mod;
	rc.val = (rc.val + t.tag * p2[rc.len-1] % mod) % mod;
	lc.maxn += t.tag;
	rc.maxn += t.tag;
	lc.tag += t.tag;
	rc.tag += t.tag;
	t.tag = 0;
}
void pushdown(int k) {
	pushdown(tr[k], tr[k << 1], tr[k << 1 | 1]);
}
void build(int k, int l, int r) {
	if (l == r) {
		tr[k] = { l,r,a[l],a[l],1,0 };
		return;
	}
	tr[k] = { l,r };
	ll mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	pushup(k);
}
void modify(int k, int l, int r,int val) {
	if (tr[k].l >= l && tr[k].r <= r && tr[k].maxn < p) {
		tr[k].val = (tr[k].val + val * p2[tr[k].len-1] % mod) % mod;
		tr[k].maxn += val;
		tr[k].tag += val;
		return;
	}
	if (tr[k].l == tr[k].r) {
		tr[k].val = tr[k].maxn = 0;
		return;
	}
	pushdown(k);
	ll mid = (tr[k].l + tr[k].r) >> 1;
	if (l <= mid)modify(k << 1, l, r, val);
	if (r > mid)modify(k << 1 | 1, l, r, val);
	pushup(k);
}
Node query(int k, int l, int r) {
	if (tr[k].l >= l && tr[k].r <= r)
		return tr[k];
	pushdown(k);
	ll mid = (tr[k].l + tr[k].r) >> 1;
	if (r <= mid)return query(k << 1, l, r);
	else if (l > mid)return query(k << 1 | 1, l, r);
	else {
		auto lc = query(k << 1, l, r);
		auto rc = query(k << 1 | 1, l, r);
		Node res;
		pushup(res, lc, rc);
		return res;
	}
}
void solve() {
	cin >> n >> m;
	p1[0] = p2[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		p1[i] = p1[i - 1] * base % mod;
		p2[i] = (p2[i - 1] * base + 1) % mod;
	}
	build(1, 1, n);
	for (int i = 1; i <= m; i++) {
		int op;
		cin >> op;
		if (op == 1) {
			int l, r;
			cin >> l >> r;
			modify(1, l, r, 1);
		}
		else {
			int x, y, len;
			cin >> x >> y >> len;
			bool ans = query(1, x, x + len - 1).val == query(1, y, y + len - 1).val;
			cout << (ans == 1 ? "yes\n" : "no\n");
		}
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	while (t--)
		solve();
}