Task 4

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

class PersistentSegmentTree {
private:
    struct Node {
        int left;
        int right;
        int value;

        Node() : left(-1), right(-1), value() {}
    };

    int n;
    vector<int> t;
    vector<Node> g;

    int clone(int v) {
        int c = g.size();
        g.emplace_back();
        if (v != -1) {
            g[c].left = g[v].left;
            g[c].right = g[v].right;
            g[c].value = g[v].value;
        }
        return c;
    }

    int get(int v) {
        if (v == -1)
            return 0;
        return g[v].value;
    }

    void update(int v, int l, int r, int p, int x) {
        if (l + 1 == r) {
            g[v].value = x;
            return;
        }
        int m = (l + r) / 2;
        if (p < m) {
            int c = clone(g[v].left);
            g[v].left = c;
            update(c, l, m, p, x);
        } else {
            int c = clone(g[v].right);
            g[v].right = c;
            update(c, m, r, p, x);
        }
        g[v].value = get(g[v].left) + get(g[v].right);
    }

    int query(int v, int l, int r, int lq, int rq) {
        if (v == -1 || lq >= rq)
            return 0;
        if (lq == l && rq == r)
            return get(v);
        int m = (l + r) / 2;
        int ls = query(g[v].left, l, m, lq, min(rq, m));
        int rs = query(g[v].right, m, r, max(lq, m), rq);
        return ls + rs;
    }

public:
    PersistentSegmentTree(int n) : n(n), t() {
        t.emplace_back();
        g.emplace_back();
        t.reserve(2e6);
        g.reserve(22e6);
    }

    int query(int l, int r, int v) {
        return query(t[v], 0, n, l, r);
    }

    int update(int p, int x) {
        int v = t.size();
        int c = clone(t.back());
        t.push_back(c);
        update(c, 0, n, p, x);
        return v;
    }
};

int main() {
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n, q;
    scanf("%d%d", &n, &q);
    vector<pair<int, int>> a(n);
    int maxa = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
        maxa = max(maxa, a[i].first);
    }
    sort(a.begin(), a.end());
    vector<int> vers(16e5);
    PersistentSegmentTree tree(n);
    for (const auto& p : a) {
        vers[p.first] = tree.update(p.second, 1);
    }
    for (int i = 1; i < vers.size(); i++) {
        if (vers[i] == 0)
            vers[i] = vers[i - 1];
    }
    for (int i = 0; i < q; i++) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int x;
            scanf("%d", &x);
            if (x > 0)
                vers[x] = vers[x - 1];
        }
        if (t == 2) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", tree.query(l - 1, r, vers[x]));
        }
    }
    return 0;
}