Kth one

#include <iostream>
#define int long long
using namespace std;

const int N = 2e5 + 5;

int n, q, a[N], t[4 * N];

///O(n)
///we want to calculate value for vertex v which represents the range [vl; vr]
void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = a[vl];
        return;
    }
    int vm = (vl + vr) / 2;
    ///calculate left son
    build(2 * v, vl, vm);
    ///calculate right son
    build(2 * v + 1, vm + 1, vr);

    ///combine them
    t[v] = t[2 * v] + t[2 * v + 1];
}


///O(log n)
void update(int v, int vl, int vr, int pos, int val) {
    if (vl == vr) {
        ///vl == vr == pos
        t[v] = val;
        a[vl] = val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= vm)
        ///the position in the left half => calculate left son
        update(2 * v, vl, vm, pos, val);
    else
        ///the position in the right half => calculate right son
        update(2 * v + 1, vm + 1, vr, pos, val);

    ///combine them
    t[v] = t[2 * v] + t[2 * v + 1];
}

int find_kth(int v, int vl, int vr, int k) {
    if (vl == vr)
        return vl;

    int vm = (vl + vr) / 2;
    if (t[2 * v] >= k)
        return find_kth(2 * v, vl, vm, k);
    else
        return find_kth(2 * v + 1, vm + 1, vr, k - t[2 * v]);
}


signed main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int pos;
            cin >> pos;
            int val;
            if (a[pos] == 0)
                val = 1;
            else
                val = 0;

            update(1, 1, n, pos, val);
        } else {
            int k;
            cin >> k;
            cout << find_kth(1, 1, n, k) << "\n";
        }
    }

    return 0;
}