Which Array Positions End Up Changed?

For each index i, the value a[i] describes an update whose right endpoint is i. The update marks a continuous block ending at i. If a[i] >= i, the block runs from 1 to i because it would otherwise pass the left edge. If 0 < a[i] < i, it covers exactly a[i] positions, from i - a[i] + 1 to i. A value of 0 contributes no interval.

Rather than applying every update directly, keep a difference array b. An update on [l, i] does b[l]++ and b[i+1]--. After all updates are recorded, a prefix sum over b gives the number of intervals covering each position. Positions with a nonzero count are printed as 1; the rest as 0. The b array is reset for each test case.

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

const int N = 1e6 + 3;

int a[N], b[N];

void solve(){
    int n; cin >> n;
    for(int i = 1; i <= n; i ++){
        b[i] = 0;  // reset
        cin >> a[i];  // record the operation
    }
    for(int i = 1; i <= n; i ++){
        if(a[i] >= i) b[1] ++, b[i + 1] --;  // a[i] is out of range, so the entire current range is affected
        else if(a[i] < i && a[i] != 0) b[i - a[i] + 1] ++, b[i + 1] --;  // otherwise a[i] elements are affected, starting from position i - a[i] + 1
    }
    for(int i = 1; i <= n; i ++){
        b[i] += b[i - 1];  // prefix sum computes how many times each position is affected
        if(b[i] != 0) cout << 1 << ' ';  // nonzero means this position has been affected
        else cout << 0 << ' ';
    }
    cout << endl;
}

int main(){
    int _; cin >> _;
    while(_ --) solve();
    return 0;
}

Each test case takes O(n) time: one pass to read and reset, one pass to record intervals, and one pass to build prefix sums. The difference array uses O(n) space, and the input array is also stored.