#include #define long long long int #define DEBUG using namespace std; // @author: pashka int n; set keys; set mins; struct fenwick { vector f; void init(int n) { f.assign(n + 1, 0); } long sum(int r) { // exclusive if (r == 0) return 0; r--; long result = 0; for (; r >= 0; r = (r & (r + 1)) - 1) result += f[r]; return result; } void inc(int i, long x) { for (; i < f.size(); i = (i | (i + 1))) f[i] += x; } }; fenwick ft; fenwick bads; vector bad; long get_value(int i) { return ft.sum(i + 1); } set mins_to_check; void check_key(int i) { if (i == 0 || i == n + 1) { return; } // cout << "check_key " << i << "\n"; if (get_value(i) != get_value(i - 1)) { keys.insert(i); mins_to_check.insert(i); auto p = keys.find(i); ++p; mins_to_check.insert(*p); --p; --p; mins_to_check.insert(*p); } else { keys.erase(i); auto p = keys.lower_bound(i); mins_to_check.insert(*p); --p; mins_to_check.insert(*p); } } set bads_to_check; void check_min(int i) { if (i == 0 || i == n + 1) return; // cout << "check_min " << i << "\n"; if (keys.find(i) != keys.end()) { bads_to_check.insert(i); auto p = keys.find(i); ++p; bads_to_check.insert(*p); --p; --p; bads_to_check.insert(*p); } else { mins.erase(i); bads_to_check.insert(i); auto p = keys.lower_bound(i); bads_to_check.insert(*p); --p; bads_to_check.insert(*p); } long cur = get_value(i); auto p = keys.find(i); ++p; long nx = get_value(*p); --p; --p; long pr = get_value(*p); if (cur < pr && cur < nx) { mins.insert(i); } else { mins.erase(i); } } void check_bad(int i) { if (i == 0 || i == n + 1) { return; } // cout << "check_bad " << i << "\n"; if (mins.find(i) == mins.end()) { if (bad[i]) { bad[i] = false; bads.inc(i, -1); } return; } auto p = mins.lower_bound(i + 1); long nx = get_value(*p); long cur = get_value(i); // cout << "! " << cur << " " << nx << "\n"; if (cur >= nx) { if (!bad[i]) { bad[i] = true; bads.inc(i, 1); } } else { if (bad[i]) { bad[i] = false; bads.inc(i, -1); } } } void increment(int l, int r, long d) { ft.inc(l, d); ft.inc(r, -d); set key_to_check; key_to_check.insert(l); key_to_check.insert(r); auto p = keys.lower_bound(r); p--; key_to_check.insert(*p); mins_to_check.clear(); for (int i : key_to_check) { check_key(i); } // cout << "keys: "; // for (int x : keys) cout << x << " "; cout << "\n"; p = mins.lower_bound(l); mins_to_check.insert(*p); p = mins.lower_bound(r); --p; mins_to_check.insert(*p); bads_to_check.clear(); for (int i : mins_to_check) { check_min(i); } // cout << "mins: "; // for (int x : mins) cout << x << " "; cout << "\n"; for (int i : bads_to_check) { check_bad(i); } } int main() { ios::sync_with_stdio(false); cin >> n; vector a(n + 2); for (int i = 0; i < n; i++) { cin >> a[i + 1]; } a[0] = a[n + 1] = INT_MIN; ft.init(n + 2); ft.inc(0, a[0]); for (int i = 1; i < n + 2; i++) { ft.inc(i, a[i] - a[i - 1]); } keys.insert(0), keys.insert(n + 1); mins.insert(0), mins.insert(n + 1); bads.init(n + 2); bad.resize(n + 2); for (int i = 1; i <= n; i++) { check_key(i); } for (int i : keys) { check_min(i); } for (int i : mins) { check_bad(i); } int q; cin >> q; // for (auto x : bad) cout << x; cout << "\n"; // cout << "\n"; const long INF = 1e17; while (q--) { string s; cin >> s; if (s == "check") { int l, r; cin >> l >> r; r++; increment(l, r, -INF); // for (auto x : bad) cout << x; cout << "\n"; if (bads.sum(r) == bads.sum(l)) { cout << "YES\n"; } else { cout << "NO\n"; } increment(l, r, INF); } else { int l, r, d; cin >> l >> r >> d; r++; increment(l, r, d); } } return 0; }