Observation 1

For 3 operations $X$, $Y$, $Z$ in order, if $Y$ can't undo $X$ and $Z$ can't undo $Y$, then $Z$ can't undo $X$.

This observation is pretty obvious and doesn't seem very helpful at first, but it will become useful later on.

Before we move on though, view each operation as a node in a graph. If $Y$ undoes $X$, draw an edge between $Y$ and $X - 1$ and let $P_Y = X - 1$.

Notice how the answer for $Y$ is simply the answer for $P_Y$. Additionally, our graph is a forest.

Here's the graph for the sample test case:

Observation 2

If $Y$ can't undo $X$, then $Y$ can't undo any operation in the range $(P_X, X]$.

This is because $P_X + 1$ is the most recent active operation $X$ could undo. The states of the operations in the range $(P_X, X]$ also remain unchanged after applying operation $X$, so by observation 1, this is true. (This still holds when we undo some operations.)

Observation 3

By observation 2, the operation we undo must lie on some path from the most recent operation upwards!

We essentially want the most recent operation with level strictly less than the current undo. We can use suffix minimums and binary lifting to find this operation.

Complexity

Time: $O(N \log N)$.

Memory: $O(N \log N)$.

Code

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int anc[300001][20], mn[300001][20], ans[300001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

Alternative (Ben)

Let lev[x]=max(0,-a[x]).

Let active_y[x]=true if operation x is active after y operations, and false otherwise. Obviously active_y[y]=true.

Let activepath_y[x]=true if operation x could possibly be undone after another operation, and false otherwise. In other words, active_y[x]=true and no z>x exists with active_y[z]=true and lev[z]<=lev[x]. If this is the case, we'll say that "x lies on the active path of y." Obviously, activepath_y[y]=true.

Claim: If activepath_y[x] then active_y[1..x]=active_x[1..x].

Proof: We use induction. Suppose that this is true for y=1..q and we we want to prove it for y=q+1. If lev[q+1]=0 then q+1 is the only vertex on the active path for q+1, so this obviously holds. Otherwise, assume that operation q+1 undoes operation z on the active path for q. By the inductive hypothesis, active_q[1..z]=active_z[1..z], which implies that active_{q+1}[1..z-1]=active_{z-1}[1..z-1].

All operations on the active path for q+1 aside from q+1 itself also lie on the active path for z-1. Also, for any t on the active path for z-1, active_t[1..t]=active_{z-1}[1..t]=active_{q+1}[1..t]. This completes the proof.

So the solution is to maintain the active path for every i. If there exists an operation with level 0 on the active path for i, then its state is the answer for i; otherwise, the answer for i is 0.

int state[MX], par[MX][19], lev[MX];

int getPar(int x, int maxLev) { // get last op on active path of x with lev <= maxLev
    if (lev[x] <= maxLev) return x;
    R0F(i,19) if (lev[par[x][i]] > maxLev) x = par[x][i];
    return par[x][0];
}

int main() {
    setIO();