Idea

Let $t$ be the number of type-2 queries processed so far.

For each index $i$, while $A_i>0$, define

$$D_i=t+A_i.$$

Think of $D_i$ as the time when $A_i$ reaches zero if we keep applying type-2 queries.

Under a type-2 operation, $t$ increases by $1$, but $D_i$ does not change for positive elements:

$$A_i=D_i-t.$$

If $D_i\le t$, then $A_i=0$.

The remaining problem is to update the XOR efficiently when every positive value decreases by one.

---

For any positive integer $x$,

$$x\oplus(x-1)$$

has bit $k$ set exactly when $2^k\mid x$.

Therefore, when every positive $A_i$ is decreased by $1$, bit $k$ of the total XOR flips iff

$$\#\{i:A_i>0,\ 2^k\mid A_i\}$$

is odd.

But

$$A_i=D_i-t,$$

so

$$2^k\mid A_i \iff D_i\equiv t\pmod {2^k}.$$

Thus, for every $k$, maintain the parity of the number of active deadlines $D_i$ for each residue modulo $2^k$.

There are only

$$1+2+4+\cdots+2^{\lfloor\log_2 Q\rfloor}=O(Q)$$

such residue slots in total.

C++17

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    // Bits that can occur in values <= Q.
    int K = 0;
    while ((1 << K) <= Q) ++K;

    // parity[k][r]:
    // parity of the number of active deadlines D
    // satisfying D % 2^k == r.
    vector<vector<unsigned char>> parity(K);
    for (int k = 0; k < K; ++k) {
        parity[k].assign(1 << k, 0);
    }

    // deadline[i] is meaningful as an active deadline iff deadline[i] > t.
    vector<int> deadline(N, 0);

    // Number of active elements having exactly this deadline.
    vector<int> cnt(Q + 2, 0);

    int t = 0;
    int xr = 0;

    // Toggle the contribution of one deadline in all parity tables.
    auto toggle = [&](int d) {
        for (int k = 0; k < K; ++k) {
            int mask = (1 << k) - 1;
            parity[k][d & mask] ^= 1;
        }
    };

    while (Q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int x;
            cin >> x;
            --x;

            int d = deadline[x];

            if (d > t) {
                // Currently A[x] = d - t > 0.
                int a = d - t;

                // Replace a by a+1 in the total XOR.
                xr ^= a;
                xr ^= (a + 1);

                // Move its deadline d -> d+1.
                --cnt[d];
                toggle(d);

                ++d;
                deadline[x] = d;

                ++cnt[d];
                toggle(d);
            } else {
                // Currently A[x] = 0.
                // It becomes 1, hence deadline t+1.
                xr ^= 1;

                int nd = t + 1;
                deadline[x] = nd;

                ++cnt[nd];
                toggle(nd);
            }
        } else {
            // Before increasing t, every active A_i is positive.
            //
            // Bit k flips iff the number of active D_i satisfying
            // D_i == t (mod 2^k) is odd.
            for (int k = 0; k < K; ++k) {
                int mask = (1 << k) - 1;
                int residue = t & mask;

                if (parity[k][residue]) {
                    xr ^= (1 << k);
                }
            }

            ++t;

            // Deadlines equal to the new t have just reached A_i = 0.
            // Remove all of them from the active parity structures.
            //
            // Since the structures store parity, removing cnt[t]
            // identical entries matters only when cnt[t] is odd.
            if (cnt[t] & 1) {
                toggle(t);
            }
            cnt[t] = 0;
        }

        cout << xr << '\n';
    }

    return 0;
}

Why it is correct

For a positive value $x$,

$$x\oplus(x-1)=2^{v_2(x)+1}-1,$$

where $v_2(x)$ is the largest $e$ such that $2^e\mid x$. Hence bit $k$ changes during $x\to x-1$ exactly when $2^k\mid x$.

So during query type 2, bit $k$ of the XOR changes once for every positive $A_i$ divisible by $2^k$. Only the parity of their count matters.

Because active elements satisfy

$$A_i=D_i-t,$$

we have

$$2^k\mid A_i \iff D_i\bmod 2^k=t\bmod2^k.$$

parity[k][t mod 2^k] stores precisely the parity we need, so the type-2 update of xr is correct.

For a type-1 query, only one value changes from $a$ to $a+1$, so

$$\text{XOR}_{new} = \text{XOR}_{old}\oplus a\oplus(a+1),$$

which is exactly what the code performs.

Complexity

There are $O(\log Q)$ residue levels.

• Type 1: $O(\log Q)$
• Type 2: $O(\log Q)$
• Total: $O(Q\log Q+N)$
• Memory: $O(N+Q)$

This comfortably handles $N,Q\le5\times10^5$.