算法

(贪心) $O(n + q)$

由于 $a$ 数组中只包含 0 和 1，所以我们只需统计 $1$ 的个数即可，因为数组 $a$ 按非升序排序后，1 都在左边，而 0 都在右边。对于操作1，如果 x 位置上的数为1，那么 1 的个数将减少一个，否则将增加一个，同时按题目要求令 $a[x] = 1 - a[x]$；对于操作2，我们只需判断 x 是否在左边的 1 的范围内即可。

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;

int main() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    int c = 0;
    for (auto& x : a) {
        cin >> x;
        c += x;
    }

    while (q--) {
        int t, x;
        cin >> t >> x;
        --x;
        if (t == 1) {
            if (a[x]) --c;
            else ++c;
            a[x] = 1 - a[x];
        }
        else {
            cout << (c > x ? "1\n" : "0\n");
        }
    }

    return 0;
}