原题链接
定义(f(S)=去除所有括号珂以匹配的子串后的剩下的字符串)，例如：(f())[]([)]([])[[())=)([)][[。
若(S)中含有交错的括号序列，如([)]，则称(S)为WBS(wrong brackets sequence)。
如果字符串(S)是一个CBS(correct brackets sequence)，则(f(S)=operatorname {null})
否则，那么(f(S))必然会有一下3种情况：
-
(f(S))是WBS
-
(f(S))左侧有多余的右括号
-
(f(S))右侧有多余的左括号
我们考虑用线段树维护(f(S))。
先想想合并两个字符串(S_l,S_r)需要用到哪些东西
首先要有一个玩意儿来判断(S)是否是WBS，因为两个WBS合并后也是一个WBS。然后就要处理左右括号的问题。
只有(S_r)的左边的右括号有珂能和(S_l)的右边的右括号合并。这要满足(S_l)的右边的左括号和(S_r)的左边的右括号的括号类型是相同的。
所以，我们维护线段树上的字符串(S)，需要用到(3)个东西：
-
一个
boolean值(判断(S)是否为WBS) -
一个字符串(l)，代表(S)左边的右括号
-
一个字符串(r)，代表(S)右边的左括号
直接维护(l,r)显然代价太大了，考虑用可持久化treap维护这两个玩意儿。
因为我们要判断(S_l)右边的左括号和(S_r)左边的右括号是否匹配，所以我们还需要在可持久化treap上维护字符串的hash值。
至于为什么要用可持久化treap，我来解释一下：
-
(S_l)的右边的左括号的长度和(S_r)的左边的右括号的长度是不确定的，我们需要来裁剪一段最长的字符串来看是否匹配，如果匹配，还要把匹配的部分删掉，这是线段树所不能做的事情
-
如果你用的是treap而不是可持久化treap，在线段树父级节点删除匹配的部分的时候，子节点也会一起把那个删掉。所以要用可持久化treap克隆一下节点。
贴一下代码：
// Code by H~$~C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdint.h>
#include <stdbool.h>
#include <time.h>
#define lambda(return_type, function_body) ({ return_type $this function_body $this; })
#define $ lambda // it won't allow comma (that is ',') without brackets in the function body!
#define inline __attribute__((__always_inline__)) __inline
#define eprintf(...) (fprintf(stderr, __VA_ARGS__) & fflush(stderr))
#define max(a, b) ({ __typeof(a) _A = a, _B = b; (_A > _B) ? a : b; })
#define min(a, b) ({ __typeof(a) _A = a, _B = b; (_A < _B) ? a : b; })
#define swap(a, b) ({ __typeof(a) _swap_tmp = a; a = b; b = _swap_tmp; 0; })
typedef long long int64;
typedef unsigned long long hash_type;
const hash_type BASE = 100003;
const hash_type MOD = 1000000007;
#define Maxn 100005
int n, k, q;
int a[Maxn];
bool lb[Maxn];
hash_type pw[Maxn];
// treap
#define T_Maxn 3000000
#define T_RMaxn 2950000
typedef struct {
int size, fix;
int l, r;
int key;
hash_type hash;
} t_node;
int total_node;
#define ls tr[p].l
#define rs tr[p].r
t_node tr[T_Maxn];
inline void t_clear() {
total_node = 0;
tr[0].size = tr[0].fix = 0;
tr[0].l = tr[0].r = 0;
tr[0].key = 0;
tr[0].hash = 0;
}
inline void t_initialize(int p, int v) {
tr[p].size = 1;
tr[p].fix = ((rand() << 15) | rand());
tr[p].l = tr[p].r = 0;
tr[p].key = v;
tr[p].hash = v;
}
#define t_newnode(...)
({
t_initialize(++total_node, __VA_ARGS__);
total_node;
})
#define t_clone(p) ({ tr[++total_node] = tr[p]; total_node; })
inline void t_pushup(int p) {
if (!p) return ;
tr[p].size = tr[ls].size + tr[rs].size + 1;
tr[p].hash = (tr[ls].hash * pw[tr[rs].size + 1] + tr[p].key * pw[tr[rs].size] + tr[rs].hash) % MOD;
}
int t_merge(int l, int r) {
if (!l || !r) return l | r;
if (tr[l].fix < tr[r].fix) {
l = t_clone(l);
tr[l].r = t_merge(tr[l].r, r);
t_pushup(l);
return l;
}
else {
r = t_clone(r);
tr[r].l = t_merge(l, tr[r].l);
t_pushup(r);
return r;
}
}
void t_split(int p, int s, int *l, int *r) {
if (!p) *l = *r = 0;
else {
p = t_clone(p);
int lsize = tr[ls].size + 1;
if (lsize <= s) {
*l = p;
t_split(rs, s - lsize, &tr[*l].r, r);
t_pushup(*l);
}
else {
*r = p;
t_split(ls, s, l, &tr[*r].l);
t_pushup(*r);
}
}
}
#undef ls
#undef rs
bool usl[Maxn << 2];
int lf[Maxn << 2], rf[Maxn << 2];
#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid ((l + r) >> 1)
void merge_answers(bool usl, bool usr, int l1, int r1, int l2, int r2, bool *us, int *l, int *r) {
*us = usl || usr;
if (*us) return ;
int A, B;
if (tr[r1].size >= tr[l2].size) {
t_split(r1, tr[r1].size - tr[l2].size, &A, &B);
if (tr[B].hash != tr[l2].hash) *us = 1;
else {
*us = 0;
*l = l1;
*r = t_merge(A, r2);
}
}
else {
t_split(l2, tr[l2].size - tr[r1].size, &A, &B);
if (tr[B].hash != tr[r1].hash) *us = 1;
else {
*us = 0;
*l = t_merge(A, l1);
*r = r2;
}
}
}
inline void pushup(int p) {
merge_answers(usl[ls], usl[rs], lf[ls], rf[ls], lf[rs], rf[rs], usl + p, lf + p, rf + p);
}
inline void apply(int p, int id) {
lf[p] = rf[p] = usl[p] = 0;
if (lb[id]) rf[p] = t_newnode(a[id]);
else lf[p] = t_newnode(a[id]);
}
void build(int p, int l, int r) {
if (l == r)
return apply(p, l);
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(p);
}
void modify(int p, int l, int r, int pos, int v, bool dir) {
if (l == r) {
a[l] = v;
lb[l] = dir;
return apply(p, l);
}
if (pos <= mid)
modify(ls, l, mid, pos, v, dir);
else
modify(rs, mid + 1, r, pos, v, dir);
pushup(p);
}
bool query(int p, int l, int r, int L, int R, int *nlf, int *nrf) {
if (L > r || l > R) {
*nlf = *nrf = 0;
return false;
}
if (L <= l && r <= R) {
*nlf = lf[p];
*nrf = rf[p];
return usl[p];
}
int nlf1 = 0, nlf2 = 0, nrf1 = 0, nrf2 = 0;
bool usl1 = query(ls, l, mid, L, R, &nlf1, &nrf1);
bool usl2 = query(rs, mid + 1, r, L, R, &nlf2, &nrf2);
bool usl0 = false;
merge_answers(usl1, usl2, nlf1, nrf1, nlf2, nrf2, &usl0, nlf, nrf);
return usl0;
}
int main() {
srand(time(NULL));
pw[0] = 1ULL;
for (int i = 1; i < Maxn; ++i)
pw[i] = pw[i - 1] * BASE % MOD;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
lb[i] = (a[i] > 0);
if (a[i] < 0) a[i] = -a[i];
}
build(1, 1, n);
scanf("%d", &q);
while (q--) {
int op;
scanf("%d", &op);
if (op == 1) {
int x, v;
scanf("%d%d", &x, &v);
modify(1, 1, n, x, v > 0 ? v : -v, v > 0);
}
else {
int l, r;
scanf("%d%d", &l, &r);
int nlf = 0, nrf = 0;
bool ans = query(1, 1, n, l, r, &nlf, &nrf);
puts((ans || nlf || nrf) ? "No" : "Yes");
}
if (total_node >= T_RMaxn) {
total_node = 0;
build(1, 1, n);
}
}
return 0;
}