Lucky prefixes

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define D(x) {x;}
#else
#define D(x)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int) (x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

struct S {
    bool en = 0;
    long tot = 0;
    long mpref = 0;
};

S operator+(S a, S b) {
    if (!a.en) return b;
    if (!b.en) return a;
    return {1, a.tot + b.tot, min(a.mpref, a.tot + b.mpref)};
}

const int N = 1<<18;

S sp[2*N];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        sp[N+i] = {1, x, x};
    }
    for (int i = N-1; i > 0; --i) {
        sp[i] = sp[2*i] + sp[2*i+1];
    }
    for (int qi = 0; qi < q; ++qi) {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 1) {
            int x = N+a-1;
            sp[x] = {1, b, b};
            while (x /= 2) sp[x] = sp[2*x] + sp[2*x+1];
        } else {
            a--; b--;
            a += N; b += N;
            S l{}, r{};
            while (a <= b) {
                // D(cerr << a << " " << b << endl);
                if (a&1) l = l + sp[a++];
                if (~b&1) r = sp[b--] + r;
                a /= 2; b /= 2;
            }
            // D(cerr << l.tot << " " << l.mpref << " " << r.tot << " " << r.mpref << endl);
            S tot = l + r;
            if (tot.mpref >= 0) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED