y总在视频里讲了一个标记持久化的做法，自己尝试写了一个使用常规懒标记的做法

比y总做法慢了将近一倍…不过还是能过

线段树的动态开点放在了pushdown函数里面

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
const int N = 50010, M = N * 17 * 17;
int n, m;
struct Node1{
    int l, r;
    int sum, add;
} tr1[M];
struct Node2{
    int l, r;
    int t;
} tr2[N * 4];
struct Q{
    int t, a, b, c;
} q[N];
vector<int> v;
int idx;

int get(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

void pushdown(int u, int l, int r)
{
    if(!tr1[u].l) tr1[u].l = ++idx;
    if(!tr1[u].r) tr1[u].r = ++idx;
    auto& root = tr1[u], &left = tr1[tr1[u].l], &right = tr1[tr1[u].r];
    if(root.add)
    {
        int mid = l + r >> 1;
        left.add += root.add, left.sum += (mid - l + 1) * root.add;
        right.add += root.add, right.sum += (r - mid) * root.add;
        root.add = 0;
    }
}

void pushup(int u)
{
    tr1[u].sum = tr1[tr1[u].l].sum + tr1[tr1[u].r].sum;
}

void update(int u, int l, int r, int ql, int qr)
{
    if(l >= ql && r <= qr) tr1[u].sum += r - l + 1, ++tr1[u].add;
    else
    {
        int mid = l + r >> 1;
        pushdown(u, l, r);
        if(ql <= mid) update(tr1[u].l, l, mid, ql, qr);
        if(qr > mid) update(tr1[u].r, mid + 1, r, ql, qr);
        pushup(u);
    }
}

int get_cnt(int u, int l, int r, int ql, int qr)
{
    if(l >= ql && r <= qr) return tr1[u].sum;
    int mid = l + r >> 1;
    pushdown(u, l, r);
    int res = 0;
    if(ql <= mid) res += get_cnt(tr1[u].l, l, mid, ql, qr);
    if(qr > mid) res += get_cnt(tr1[u].r, mid + 1, r, ql, qr);
    return res;
}

void build(int u, int l, int r)
{
    tr2[u] = {l, r, ++idx};
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int v)
{
    update(tr2[u].t, 1, n, l, r);
    if(tr2[u].l == tr2[u].r) return;
    int mid = tr2[u].l + tr2[u].r >> 1;
    if(v <= mid) modify(u << 1, l, r, v);
    else modify(u << 1 | 1, l, r, v);
}

int query(int u, int l, int r, int k)
{
    if(tr2[u].l == tr2[u].r) return tr2[u].l;
    int mid = tr2[u].l + tr2[u].r >> 1;
    int cnt = get_cnt(tr2[u << 1 | 1].t, 1, n, l, r);
    if(cnt >= k) return query(u << 1 | 1, l, r, k);
    return query(u << 1, l, r, k - cnt);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d%d", &q[i].t, &q[i].a, &q[i].b, &q[i].c);
        if(q[i].t == 1) v.push_back(q[i].c);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    build(1, 0, v.size() - 1);
    for(int i = 0; i < m; ++i)
    {
        if(q[i].t == 1) modify(1, q[i].a, q[i].b, get(q[i].c));
        else printf("%d\n", v[query(1, q[i].a, q[i].b, q[i].c)]);
    }
    return 0;
}