\(A\) の総 \(\mathrm{XOR}\) を \(f(A)\) と表します。各クエリでは変更後の \(A\) に対する \(f(A)\) の値を求めれば良いです。

まずクエリ \(2\) が与えられない場合を考えます。この場合、\(A_x\) に \(1\) 足される前の \(f(A)\) を \(X\) とすると、足された後の \(f(A)\) は変更前の \(A_x\) を用いて \(X \oplus A_x \oplus (A_x+1)\) と表せます。この差分の計算は高速に行うことができるので、全体としても高速に計算できます。より一般に、\(A\) の \(1\) つの項に適当な値を加算・減算した後の \(f(A)\) の値も高速に計算できます。

このことを用いてクエリ \(2\) が与えられる場合も考えます。

毎回 \(N\) 個の値に対して \(A_i \geq 1\) かを判定すると TLE となります。そこで、\(A_i \geq 1\) であるような \(i\) の集合を保持することを考えます。

クエリ \(1\) ではこの集合は変わらないか \(1\) つ要素が追加されるかのいずれかです。

クエリ \(2\) ではこの保持している集合内の添字 \(i\) それぞれに対し \(A_i\) から \(1\) を引きます。そして、その中から再度集合を構築し直します（つまり、新たに \(A_i=0\) となった要素は集合から除外する）。

はじめ \(A\) の要素は全て \(0\) であることを考えると、これらの操作は全体で計算量が \(O(N+Q)\) に抑えられることが分かります。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

input = __import__("sys").stdin.readline
n, q = map(int, input().split())
idxs = []
a = [0] * n
ans = 0
for _ in range(q):
    data = list(map(int, input().split()))
    if data[0] == 1:
        x = data[1] - 1
        if a[x] == 0:
            idxs.append(x)
        ans ^= a[x] ^ (a[x] + 1)
        a[x] += 1
    else:
        for v in idxs:
            ans ^= a[v] ^ (a[v] - 1)
            a[v] -= 1
        idxs = [v for v in idxs if a[v] != 0]
    print(ans)