提交时间:2024-10-02 20:00:32
运行 ID: 33021
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 9; #define ls(u) (u << 1) #define rs(u) (u << 1 | 1) int n, q, a[N], b[N]; struct seg { int mn[N << 2], lz[N << 2]; void pu(int u) { mn[u] = min(mn[ls(u)], mn[rs(u)]); } void build(int u, int l, int r, int tp) { if (l == r) { mn[u] = ((l & 1) == tp ? b[l] : (int)1e9); return; } int mid = (l + r) >> 1; build(ls(u), l, mid, tp), build(rs(u), mid + 1, r, tp); pu(u); } void pd(int u) { mn[ls(u)] += lz[u], mn[rs(u)] += lz[u]; lz[ls(u)] += lz[u], lz[rs(u)] += lz[u]; lz[u] = 0; } void upd(int u, int l, int r, int x, int y, int v) { if (l > r) return; if (x <= l && r <= y) { mn[u] += v, lz[u] += v; return; } pd(u); int mid = (l + r) >> 1; if (x <= mid) upd(ls(u), l, mid, x, y, v); if (y > mid) upd(rs(u), mid + 1, r, x, y, v); pu(u); } int qry(int u, int l, int r, int x, int y) { if (l > r) return 0; if (x <= l && r <= y) return mn[u]; pd(u); int mid = (l + r) >> 1, res = 1e9; if (x <= mid) res = min(res, qry(ls(u), l, mid, x, y)); if (y > mid) res = min(res, qry(rs(u), mid + 1, r, x, y)); return res; } } T[2]; int get(int u) { if (!u) return 0; return T[u & 1].qry(1, 1, n, u, u); } signed main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= n; i++) { b[i] = a[i] - 1 - b[i - 1]; } T[0].build(1, 1, n, 0), T[1].build(1, 1, n, 1); scanf("%d", &q); while (q--) { int op, l, r, x; scanf("%d%d%d", &op, &l, &r); if (op == 1) { scanf("%d", &x); T[l & 1].upd(1, 1, n, l, r, x); if ((r - l + 1) & 1) { T[l & 1].upd(1, 1, n, r + 1, n, x); T[(l & 1) ^ 1].upd(1, 1, n, r + 1, n, -x); } } else { T[l & 1].upd(1, 1, n, l, r, get(l - 1)), T[(l & 1) ^ 1].upd(1, 1, n, l, r, -get(l - 1)); if (T[0].qry(1, 1, n, l, r) < 0 || T[1].qry(1, 1, n, l, r) < 0 || get(r)) printf("No\n"); else printf("Yes\n"); T[l & 1].upd(1, 1, n, l, r, -get(l - 1)), T[(l & 1) ^ 1].upd(1, 1, n, l, r, get(l - 1)); } } fclose(stdin), fclose(stdout); return 0; }