#pragma comment(linker, "/stack:256000000") #define _crt_secure_no_deprecate #define _crt_secure_no_warnings #define _use_math_defines #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int64; typedef unsigned long long uint64; typedef pair pii; typedef pair pll; typedef pair pli; typedef pair pil; typedef pair pib; const int inf = (int) (1e9 + 1e5); const int64 linf = (int64) (2e18); const int64 base = 1003; const double eps = 1e-9; #define sq(x) ((x)*(x)) #define fail(what) {throw logic_error(string(what));} #define ASSERT(exp) {if (!(exp)) {fail("");}} #define ASSERTC(exp, what) {if (!(exp)) {fail(what);}} #define y1 fjgjf //typedef complex comp; const int mod = 998244353;//1'000'000'007; int add(int a, int b) { a += b; if (a >= mod) { a -= mod; } return a; } int sub(int a, int b) { a -= b; if (a < 0) { a += mod; } return a; } int mul(int a, int b) { return int64(a) * b % mod; } int bin_pow(int a, int b) { int res = 1; while (b) { if (b & 1) { res = mul(res, a); } b >>= 1; a = mul(a, a); } return res; } int back(int a) { return bin_pow(a, mod - 2); } int divv(int a, int b) { return mul(a, back(b)); } int tnum; struct request { bool upd; int s, f, d; }; int n, m; vector a; vector r; void init() { scanf ("%d", &n); a.resize(n); for (auto& q : a) { scanf ("%d", &q); } scanf ("%d", &m); r.resize(m); for (auto& q : r) { char s[10]; scanf ("%s", s); if (s[0] == 'u') { q.upd = true; scanf ("%d%d%d\n", &q.s, &q.f, &q.d); } else { assert(s[0] == 'c'); q.upd = false; scanf ("%d%d\n", &q.s, &q.f); } --q.s; --q.f; } } struct tnode { bool ok, suitable; int64 mn, mx; bool has_left, has_right, has_center; int64 leftest, rightest; int64 push = 0; tnode() { memset(this, 0, sizeof(tnode)); } void update(int64 d) { mn += d; mx += d; leftest += d; rightest += d; push += d; } void print() const { printf ("mn=%lld mx=%lld leftest=%lld rightest=%lld has_left=%d has_center=%d has_right=%d push=%lld ok=%d s=%d\n", mn, mx, leftest, rightest, int(has_left), int(has_center), int(has_right), push, int(ok), int(suitable)); // printf ("ok=%d s=%d leftest=%lld rightest=%lld\n", // int(ok), int(suitable), leftest, rightest); } }; vector tre; tnode merge(const tnode& tre1, const tnode& tre2) { tnode res; if (!tre1.suitable || !tre2.suitable) { return res; } int64 left_mx = -linf; if (tre1.has_center) { left_mx = max(left_mx, tre1.mx); } int64 right_mn = linf; if (tre2.has_center) { right_mn = min(right_mn, tre2.mn); } if (left_mx >= right_mn) { return res; } bool has_new_local = false; int64 new_local = 0; if (tre1.has_right || tre2.has_left) { if (tre1.has_right && tre2.has_left) { has_new_local = true; new_local = min(tre1.rightest, tre2.leftest); } else if (tre1.has_right) { if (tre1.rightest < tre2.leftest) { has_new_local = true; new_local = tre1.rightest; } } else { assert(tre2.has_left); if (tre2.leftest < tre1.rightest) { has_new_local = true; new_local = tre2.leftest; } } } if (has_new_local) { if (new_local <= left_mx || new_local >= right_mn) { return res; } } res.suitable = true; if (tre1.has_left) { left_mx = max(left_mx, tre1.leftest); } if (tre2.has_right) { right_mn = min(right_mn, tre2.rightest); } res.ok = true; if (has_new_local) { if (new_local <= left_mx || new_local >= right_mn) { res.ok = false; } } else { if (tre1.has_left && tre1.leftest >= right_mn) { res.ok = false; } if (tre2.has_right && tre2.rightest <= left_mx) { res.ok = false; } } res.leftest = tre1.leftest; res.rightest = tre2.rightest; res.has_center = tre1.has_center || tre2.has_center || has_new_local; if (res.has_center) { if (tre1.has_center) { res.mn = tre1.mn; } else if (has_new_local) { res.mn = new_local; } else { assert(tre2.has_center); res.mn = tre2.mn; } if (tre2.has_center) { res.mx = tre2.mx; } else if (has_new_local) { res.mx = new_local; } else { assert(tre1.has_center); res.mx = tre1.mx; } } if (tre1.has_center || tre1.has_right) { res.has_left = tre1.has_left; } else if (tre1.has_left) { res.has_left = true; } else { res.has_left = tre2.has_left && tre1.rightest <= tre2.leftest || !tre2.has_left && tre1.rightest < tre2.leftest; } if (tre2.has_center || tre2.has_left) { res.has_right = tre2.has_right; } else if (tre2.has_right) { res.has_right = true; } else { res.has_right = tre1.has_right && tre2.leftest <= tre1.rightest || !tre1.has_right && tre2.leftest < tre1.rightest; } if (res.has_center && res.has_right) { if (res.rightest <= res.mx) { res.suitable = res.ok = false; return res; } } if (res.ok) { if (res.has_center) { if (res.has_left) { res.ok &= (res.leftest < res.mn); } if (res.has_right) { res.ok &= (res.mx < res.rightest); } } else if (res.has_left && res.has_right) { res.ok &= (res.leftest < res.rightest); } } return res; } tnode from_element(int el) { tnode res; res.ok = res.suitable = true; res.leftest = res.rightest = el; res.has_left = res.has_center = res.has_right = false; return res; } void build(int tv, int tl, int tr) { if (tl == tr) { tre[tv] = from_element(a[tl]); return; } int tm = (tl + tr) >> 1; build(tv << 1, tl, tm); build((tv << 1) + 1, tm + 1, tr); tre[tv] = merge(tre[tv << 1], tre[(tv << 1) + 1]); } void push(int tv, int tl, int tr) { if (tre[tv].push && tl < tr) { tre[tv << 1].update(tre[tv].push); tre[(tv << 1) + 1].update(tre[tv].push); tre[tv].push = 0; } } void update(int tv, int tl, int tr, int l, int r, int64 d) { if (l > r) { return; } if (tl == l && r == tr) { tre[tv].update(d); return; } push(tv, tl, tr); int tm = (tl + tr) >> 1; update(tv << 1, tl, tm, l, min(tm, r), d); update((tv << 1) + 1, tm + 1, tr, max(tm + 1, l), r, d); tre[tv] = merge(tre[tv << 1], tre[(tv << 1) + 1]); } tnode check(int tv, int tl, int tr, int l, int r) { if (tl == l && r == tr) { return tre[tv]; } push(tv, tl, tr); int tm = (tl + tr) >> 1; if (r <= tm) { return check(tv << 1, tl, tm, l, r); } else if (l > tm) { return check((tv << 1) + 1, tm + 1, tr, l, r); } else { return merge( check(tv << 1, tl, tm, l, min(tm, r)), check((tv << 1) + 1, tm + 1, tr, max(tm + 1, l), r) ); } } void solve() { tre.resize(n * 4 + 1); build(1, 0, n - 1); for (const auto& q : r) { if (q.upd) { update(1, 0, n - 1, q.s, q.f, q.d); } else { const auto tn = check(1, 0, n - 1, q.s, q.f); //tn.print(); printf("%s\n", (tn.ok ? "YES" : "NO")); } } } void print_answer() { } void precalc() { } void run() { #ifdef _MY_DEBUG //freopen("input.txt", "rt", stdin); freopen("06.in", "rt", stdin); freopen("output.txt", "wt", stdout); #endif precalc(); int t = 1; //scanf ("%d", &t); for (tnum = 1; tnum <= t; ++tnum) { init(); solve(); print_answer(); } } signed main() { srand(94); ios_base::sync_with_stdio(false); cin.tie(0); run(); return 0; }