采用的方法是，不计算每个位置的hash值，只计算左括号右括号总体的hash值与数量。如果某次括号不匹配最终的答案也很难为0。不知道是否有hack数据(给每个括号重新赋了随机数还是不对)。拍了一晚上也没发现问题。

代码:

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define ull unsigned long long
using namespace std;
 
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
 
struct node {
	int tag, cnt[2]; ull ve[2];
	inline void ck() {
		if(tag || ve[0] || ve[1]) puts("No");
		else puts("Yes");
	}
}b[400];
 
const int N = 1e5 + 10;
ll n, m, len, id[N], a[N], bl[400], br[400];
ll stk[400], tip;
ull pw[N];
 
inline node operator + (node a, node b) {
	a.tag = a.tag | b.tag;
	if(b.cnt[0] > a.cnt[1] || a.tag || a.ve[0]) return {1, 0, 0, 0, 0};
	int ch = a.cnt[1] - b.cnt[0];
	ull tp = a.ve[1] + b.ve[0] * pw[ch];
	a.ve[1] = b.ve[1] * pw[ch] + tp; a.cnt[1] = ch + b.cnt[1];
	return a;
}
 
inline node qryx(int l, int r) {
	ull ve[2]; ve[0] = ve[1] = 0; tip = 0;
	for(int i = l; i <= r; i++) {
		if(a[i] > 0) {stk[++tip] = a[i]; continue;}
		if(tip && stk[tip] == -a[i]) tip--;
		else stk[++tip] = a[i];
	}
	bool tag = 0, flag = 0; ll ht = tip + 1;
	for(int i = 1; i <= tip; i++) {
		if(stk[i] > 0 && !flag) flag = 1, ht = i;
		if(stk[i] < 0 && flag) {tag = 1; break;}
	}
	if(tag) return {1, 0, 0, 0, 0};
	for(int i = 1; i < ht; i++) ve[0] = ve[0] * 137 + stk[i];//,printf("!%llu\n",  ve[0]);
	for(int i = tip; i >= ht; i--) ve[1] = ve[1] * 137 + stk[i];//, printf("!%llu\n", ve[1]);
	return {0, ht - 1, tip - ht + 1, ve[0], ve[1]};
}
 
int main() {
	//freopen("3.in", "r", stdin); freopen("1.out", "w", stdout);
	n = read(); m = read(); len = sqrt(n); pw[0] = 1;
	for(int i = 1; i <= N - 10; i++) pw[i] = pw[i - 1] * 137;
	for(int i = 1; i <= n; i++) a[i] = read(), id[i] = (i - 1) / len + 1;
	for(int i = 1; i <= id[n]; i++) bl[i] = (i - 1) * len + 1, br[i] = min(n, i * len);
	for(int i = 1; i <= id[n]; i++) b[i] = qryx(bl[i], br[i]); //printf("%d %lld %lld %llu %llu\n", b[i].tag, bl[i], br[i], b[i].ve[0], b[i].ve[1]);
	for(int T = read(); T; T--) {
		int opt = read(), l = read(), r = read();
		if(opt == 1) a[l] = r, b[id[l]] = qryx(bl[id[l]], br[id[l]]);
		else {
			if(id[l] == id[r]) {node v = qryx(l, r); v.ck(); continue;}
			node v = qryx(l, br[id[l]]);
			for(int i = id[l] + 1;i < id[r]; i++) v = v + b[i];
			//printf("?%d %d %d %llu %llu\n", v.tag, v.cnt[0], v.cnt[1], v.ve[0], v.ve[1]);
			v = v + qryx(bl[id[r]], r); v.ck();
		}
	}
    return 0;
}
/*
100000
2 39292 39301
2 4378 97250
*/