建模

将问题看成数轴上的$n$个点，左侧的点可以到达右侧任意点。现在共有$3$种操作：
$1$.增加一条$x$点到$y$点的有向边。
$2$.减少一条$x$点到$y$点的有向边。
$3$.查询$x$点可以到达的点的个数。

思考

由于$x \leq y$时不会有任何影响（默认左侧点可以到达右侧点），因此下面全部考虑$x>y$的情况
$1$.什么情况下$x$的可达点会增大？
若$x$能够到达前面的点$y$，那么$y$右侧的所有点可达，此时可达点增加$[y,x-1]$内的所有点
$2$.增加一条$x$点到$y$点的有向边会发生什么？
$[y,x]$ 内的所有点相互可达。eg：从任意点到达$x$，再从$x$到达$y$，再从$y$到达$[y,x]$内的任意点。
$3$.如何表示相互可达？
设计一个数组$vis$，初始化成$0$。当$[y,x]$相互可达时，$vis_y \sim vis_x$全部非0。,
$4$.对于操作$1、2$，会发生什么？
由第三点知，需要将$vis_y \sim vis_x$全部$+1$表示可达。反之将$vis_y \sim vis_x$整体$-1$。
$5$.如何求答案？
我们需要找到：从$x$出发，能够到达的最左侧的点。由第三点知：若$x$可达$y$，则$vis_y \sim vis_x$全部非0。因此我需要找到最小的$y$满足以上条件。考虑二分去找，同时我需要知道$[y,x]$范围内，$vis$数组的最小值，若最小值为0则代表不可达，反之可达。

至此，我需要有一个数据结构满足区间修，区间最值，线段树显然非常合适。同时此题还考察了线段树上二分。时间复杂度$O(nlogn)$。$tips:$如果在线段树外面写二分，时间复杂度$O(nlognlogn)$，卡一下常可以拿到$380$分。

代码

提交记录里有很多好的写法，补药穴窝

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e15;
template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }
    void half() {
        half(1, 0, n);
    }
    int findLast(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return 0;
        }
        if (l >= x && r <= y && info[p].x > 0) {
            return 0;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y);
        if (res == 0){
            res = findLast(2 * p, l, m, x, y);
        }
        return res;
    }
};

struct Tag {
    int x = 0;
    void apply(const Tag &t) & {
        x += t.x;
    }
};

struct Info {
    int x = inf;
    void apply(const Tag &t) & {
        x += t.x;
    }
};

Info operator + (const Info &a, const Info &b) {
    return {std::min(a.x, b.x)};
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n , q;
    cin >> n >> q;
    vector<Info>v;
    for (int i = 0 ; i <= n ; i ++) {
        Info tmp = {0};
        v.push_back(tmp);
    }
    LazySegmentTree<Info , Tag> Seg(v);
    for (int i = 0 ; i < q ; i ++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x , y;
            cin >> x >> y;
            if (x <= y) continue;
            Tag t = {1};
            Seg.rangeApply(y , x , t);
        }
        else if (op == 2) {
            int x , y;
            cin >> x >> y;
            if (x <= y) continue;
            Tag t = {-1};
            Seg.rangeApply(y , x , t);
        }
        else {
            int x;
            cin >> x;
            int pos = Seg.findLast(1 , 0 , n + 1 , 0 , x);
            cout << n - pos << endl;
        }
    }

}