1340F - Nastya and CBS - CodeForces Solution

# include <cstdio>
# include <algorithm>
# include <cmath>
# include <iostream>
# include <cstring>
# include <vector>
# include <map>
# include <set>
# include <queue>
using namespace std;
const int MAXN = 1e5 + 10;
const int bl = 512;
static const int N = 6e2;
int n, k, q;
int s[MAXN];
 
struct block {
	int pop[N], c0;
	int push[N], c1;
	int ok;
} o[MAXN / bl + 10];
int eql(const int * a, const int * b, const int len) { 
	for (int i = 0;i < len;++i) {
		if (a[i] != b[i]) return 0;
	}
	return 1;
}
bool ask(int l, int r) {
	static int st[MAXN];
	int top = 0;
	#define ps(x) \
		if (x > 0) { \
			st[++top] = x; \
		} else { \
			if (!top || st[top] != -x) return 0; \
			-- top; \
		}
	for (;l % bl && l <= r;++l) ps(s[l]);
	for (;l + bl - 1 <= r;l += bl) {
		block &o = ::o[l / bl];
		if (!o.ok) return 0;
		if (top < o.c0) return 0;
		if (!eql(st + top - o.c0 + 1, o.pop + N - o.c0, o.c0)) return 0;
		top -= o.c0;
		memcpy(st + top + 1, o.push + 1, o.c1 << 2);
		top += o.c1;
	}
	for (;l <= r;++l) ps(s[l]);
	return top == 0;
}
void init(int id) {
	block&o = ::o[id];
	o.c0 = o.c1 = 0;
	o.ok = 1;
	static int st[MAXN];
	int top = 0;
	const int L = id * bl, R = min(n - 1, id * bl + bl - 1);
	for (int i = L;i <= R;++i) {
		if (s[i] > 0) {
			st[++top] = s[i];
		} else {
			if (top && st[top] != -s[i]) {
				o.ok = 0;
				return ;
			} else {
				if (top) {
					-- top;
				} else {
					o.pop[N - ++o.c0] = -s[i];
				}
			}
		}
	}
	memcpy(o.push + 1, st + 1, top << 2);
	o.c1 = top;
}
 
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;
	for (int i = 0;i < n;++i) {
		cin >> s[i];
	}
	for (int i = 0;i <= (n - 1) / bl;++i) init(i);
	cin >> q;
	for (int i = 0;i < q;++i) {
		int opt, pos, v, l, r;
		cin >> opt;
		if (opt == 1) {
			cin >> pos;
			-- pos;
			cin >> s[pos];
			init(pos / bl);
		} else {
			cin >> l >> r;
			cout << (ask(l - 1, r - 1) ? "Yes" : "No") << '\n';
		}
	}
	return 0;
}