The problem can be found here

My Thought Process

Let’s begin with some small cases. Looking at $n=3$, we have the following possible arrays and the possible sums of the subarray. \(1, 1, 1 : 1, 2, 3\)

\[1, 1, 2 : 1, 2, 3, 4\] \[1, 2, 1 : 1, 2, 3, 4\] \[2, 1, 1 : 1, 2, 3, 4\] \[2, 2, 1 : 1, 2, 3, 4, 5\] \[1, 2, 2 : 1, 2, 3, 4, 5\] \[2, 1, 2: 1, 2, 3, 5\] \[2, 2, 2 : 2, 4, 6\]

Ok, some obvious things we can see that if the array is all ones, we can have subarray sums of [1, n] and if its all twos we can have all the even numbers in the same range.

The only other weird array is $2, 1, 2$ as it doesn’t have all the values in $[1. n]$.

We should think about the problem again. Why does the problem only allow for 1s and 2s? Are there something special about these numbers. If it was any number, how would the problem be different?

Parity might be important here then. Starting with our array, how might we cut some prefix and suffix to get our desired subarray sum? If we want an even array and have an even array starting sum, how does removing 1s and 2s affect the sum?

After testing another case with an even sum $2, 2, 1, 2, 1, 2, 2, 1, 2, 1$, we notice that something interesting. With the starting sum, we can always remove numbers from the beginng and end of the array to subtract two from the sum. This is clear as we can either remove two 1s or one 2. This keeps partiy and allow us to get even numbers less than the sum of the starting array.

Okay, wait, that mean if we also have an odd sum array, we could obtain all odds number less than or equal to it? This should apply to subarrays too so we just need to find a subarray thats greater than the value we need to find and having the same partiy.

Since ones change the partiy, we only need to look at where those are in the array. Finding the first one from the front or the back will allow us to change the partiy of the array while not decreasing the sum of the array too much!

Implementation

I probably should’ve thought a bit harder because it took me a while to implement but here it is.

I used a binary indexed tree to obtain sums of subarrays and allow for easy updates.

If we need to find the value of a subarray, if the array from $[1, n]$ has the same partiy was the value we need and the same parity, we output YES.

Checking the subarray sums of $[l+1,n]$ and $[1, r-1]$ allow us to change the parity from the starting array. We check to see if either ones are greater than the value we need.

To update, if the new value is the same, do nothing. Else, add to BIT and update our set with the indicies of ones.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

struct BIT {
    vector<int> bit;  // binary indexed tree, 1-index int, 0-index ext
    int n;
 
    BIT(int n) {
        this->n = n + 1;
        bit.assign(n + 1, 0);
    }
 
    BIT(vector<int> a)
        : BIT(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
 
    int sum(int idx) {
        int ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret = (ret + bit[idx]); // % MOD
        return ret;
    }
 
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
 
    void add(int idx, int delta) {
        for (++idx; idx < n; idx += idx & -idx)
            bit[idx] = (bit[idx] + delta); // % MOD
    }
};

void solve() { 
    int n, q;
    cin >> n >> q;

    BIT b(n+1);
    set<int> s;
    for(int i = 0; i < n; ++i){
        int x; cin >> x;
        b.add(i, x);
        if(x == 1){
            s.insert(i);
        }
    }

    while(q--){
        int x, y; cin >> x >> y;
        if(x == 1){
            if((b.sum(0,n-1) % 2) == (y % 2) && b.sum(0,n-1) >= y){
                cout << "YES" << endl; continue;
            }

            if(s.size() == 0){
                cout << "NO" << endl; continue;
            }

            int a = b.sum(*s.begin() + 1, n - 1);
            int a2 = b.sum(0, *s.rbegin() - 1);

            if(max(a, a2) >= y){
                cout << "YES" << endl;
            }
            else{
                cout << "NO" << endl;
            }
        }
        else{
            int z; cin >> z;
            y--;
            if(b.sum(y, y) == z){continue;}
            
            b.add(y, z - b.sum(y, y));

            if(z == 1){
                s.insert(y);
            }
            else{
                s.erase(y);
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

See here for the solution and another implementation.