D сборы мск день 1

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef long double ld;

#define mp make_pair
#define all(x) (x).begin(), (x).end()

const int MAXN = 1e6 + 15;

int pref[MAXN], N, Q;
int res[MAXN];
int fen[MAXN];
pair<int, int> a[MAXN];

struct Query {
    int Rx, l, r, num;
    Query() : Rx(0), l(0), r(0), num(0) {}
    Query(int b, int c, int d, int r) : Rx(b), l(c), r(d), num(r) {}

    bool operator < (Query &other) {
        return Rx < other.Rx;
    }
};

Query f[MAXN];

void inc(int i, int delta) {
    for (; i < MAXN; i = (i | (i + 1)))
        fen[i] += delta;
}

int sum(int r) {
    int res = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) {
        res += fen[r];
    }
    return res;
}

int sum(int l, int r) {
    return sum(r) - sum(l - 1);
}

int main() {
    ios_base::sync_with_stdio(false);

    fill(pref, pref + MAXN, -1);

    cin >> N >> Q;

    for (int i = 0; i < N; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a, a + N);
    set<int> s;

    for (int i = 0; i < N; ++i) {
        pref[a[i].first] = i;
        s.insert(a[i].first);
    }

    int z = 0, sz = 0;

    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            if (s.count(x)) {
                s.erase(x);
                if (pref[x + 1] == -1) {
                    pref[x + 1] = pref[x];
                    s.insert(x + 1);
                }
                pref[x] = -1;
            }
        }
        else {
            int l, r, y;
            cin >> l >> r >> y;
            --l, --r;
            auto it = s.upper_bound(y);
            if (it != s.begin()) {
                --it;
                f[z++] = Query(pref[*it], l, r, sz);
            }
            sz++;
        }
    }

    sort(f, f + z);

    int ptr = -1;

    for (int i = 0; i < z; ++i) {
        while (ptr < f[i].Rx) {
            ptr++;
            inc(a[ptr].second, 1);
        }
        res[f[i].num] = sum(f[i].l, f[i].r);
    }

    for (int i = 0; i < sz; ++i) {
        cout << res[i] << "\n";
    }

    return 0;
}