P3380 树套树

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 5e4 + 5;
int n, m, cnt, totn;
int lx[N], rx[N], op[N], b[N], k[N];
int rt[N << 2], addx[N * 400]; //编号为p的权值线段树，区间线段树编号为rt[p]
LL sum[N * 400];
struct Tree{
    int L, R;
}T[N * 400];

void lazy(int p, int l, int r)
{
    int v = addx[p];
    int mid = l + r >> 1;

    if (!T[p].L) T[p].L = ++cnt;
    if (!T[p].R) T[p].R = ++cnt;
    addx[T[p].L] += v, addx[T[p].R] += v;
    sum[T[p].L] += v * (mid - l + 1), sum[T[p].R] += v * (r - mid);
    addx[p] = 0;
}

void change(int &p, int lx, int rx, int l = 1,int r = n) 
{
    if (!p) p = ++cnt;
    if (lx <= l && r <= rx) {
        ++addx[p];
        sum[p] += r - l + 1;
        return;
    }
    if (addx[p]) lazy(p, l, r);

    int mid = l + r >> 1;
    if (lx <= mid) change(T[p].L, lx, rx, l, mid);
    if (mid < rx) change(T[p].R, lx, rx, mid + 1, r);
    sum[p] = sum[T[p].L] + sum[T[p].R];
}

LL getsum(int &p, int lx, int rx, int l = 1, int r = n) 
{
    if (!p) return 0;
    if (lx <= l && r <= rx) return sum[p];
    if (addx[p]) lazy(p, l, r);
    int mid = l + r >> 1;
    LL tt = 0;
    if (lx <= mid) tt += getsum(T[p].L, lx, rx, l, mid);
    if (mid < rx) tt += getsum(T[p].R, lx, rx, mid + 1, r);
    return tt;
}

void add(int lx, int rx, int k, int p = 1, int l = 1, int r = totn) 
{
    change(rt[p], lx, rx);
    if (l == r) return;
    int mid = l + r >> 1;
    if (k <= mid) 
        add(lx, rx, k, p * 2, l, mid);
    else 
        add(lx, rx, k, p * 2 + 1, mid + 1, r);
}

int ask(int lx, int rx, LL k, int p = 1, int l = 1, int r = totn) 
{
    if (l == r) return b[l];
    int mid = l + r >> 1;
    LL tt = getsum(rt[p * 2 + 1], lx, rx);
    if (tt < k) 
        return ask(lx, rx, k - tt, p * 2, l, mid);
    else 
        return ask(lx, rx, k, p * 2 + 1, mid + 1, r);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> op[i] >> lx[i] >> rx[i] >> k[i];
        if (op[i] == 1) b[++totn] = k[i];
    }
    sort(b + 1, b + totn + 1);
    totn = unique(b + 1, b + totn + 1) - b - 1;

    for(int i = 1; i <= m; i++)
    if(op[i] == 1) k[i] = lower_bound(b + 1,b + totn + 1, k[i]) - b;

    for(int i = 1; i <= m; i++)
    {
        if(op[i] == 1) add(lx[i], rx[i], k[i]);
        else cout << ask(lx[i], rx[i], k[i]) << '\n';
    }
    return 0;
}