实际上就是区间第k小。可以用整体二分来做。

把第k次查询查询看成查询[1, i]里的第k小。把原始序列看成往第i个位置插入一个数。

二分每个询问的答案mid，对于所有操作值小于mid的加入树状数组和查询有多少个小于它的，把满足的操作放在左边，不满足的放在右边。继续分治。

要加入离散化。

总复杂度$(M + N)logN$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 233;
struct rec{ll t, x, v;};
rec a[maxn], bl[maxn], br[maxn];
ll se[maxn], qs[maxn];
set<ll> st;
ll n, m; 
unordered_map<ll,ll> ump, src;
ll c[maxn], tot;
inline void add(ll x, ll v)
{
    for(; x <= n; x += x & -x) c[x] += v;
}
inline ll ask(ll x)
{
    ll res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
ll ans[maxn];
void solve(ll lv, ll rv, ll st, ll ed)
{
    if(st > ed) return ;
    if(lv == rv)
    {
        for(register int i = st; i <= ed; ++i) ans[a[i].t] = src[lv];
        return ;
    }
    ll mid = (lv + rv) >> 1;
    int lt = 0, rt = 0;
    for(register int i = st; i <= ed; ++i)
    {
        if(a[i].t == 0) 
            if(a[i].v <= mid) add(a[i].x, 1), bl[++lt] = a[i];
            else br[++rt] = a[i];
        else 
        {
            ll tmp = ask(a[i].x);
            if(tmp >= a[i].v) bl[++lt] = a[i];
            else a[i].v -= tmp, br[++rt] = a[i];
        }
    }
    for(register int i = 1; i <= lt; ++i) a[st + i - 1] = bl[i];
    for(register int i = 1; i <= rt; ++i) a[st + lt + i - 1] = br[i]; 
    for(register int i = st; i <= ed; ++i) 
        if(a[i].t == 0)
            if(a[i].v <= mid) add(a[i].x, -1);
    solve(lv, mid, st, st + lt - 1);
    solve(mid + 1, rv, st + lt, ed); 
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &se[i]);
        st.insert(se[i]);
    }
    for(int i = 1; i <= m; i++)
    {
        scanf("%lld", &qs[i]);
    }

    for(auto it = st.begin(); it != st.end(); it++) ump[*it] = ++tot, src[tot] = *it;

    {
        int j = 0;
        for(int i = 1; i <= n; i++) a[++j] = {0, i, ump[se[i]]};
        for(int i = 1; i <= m; i++) a[++j] = {i, qs[i], i};
    }

    solve(1, tot, 1, n + m);
    for(int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}