这题我本来以为只是一道清新的小水题,然而却调了我一上午 TAT

看到区间第 k 小立刻联想到平衡树,但是问题在于这是有区间范围的嗷,每次都重新把区间里的点都加进来肯定 gg,所以就可以离线然后莫队求解

这道题要注意先插入再删除,就是说我们默认我们的左右端点 $l$ , $r$ 是在询问范围 $[ql,\ qr]$ 前的,这样子添加点肯定没有影响。但如果不这样的话,若询问给出 $[2,\ 3]$ 这样的区间,而我们的左右端点一开始是 $l = 1, r = 0$ 的,树里面也没有点,开始移动时会先删除 $l = 1$ 呀,然后 $l+1\ \to \ l=2$ ,但我们删除 $l = 1$ 就会挂啊,因为树没有节点,然后程序就会奇奇怪怪的把第一只狗的颜值弄进树了emm

另外就是很多平衡树题目题解里都会先插入 $inf$ 与 $-inf$ ,我认为部分题目其实不需要啊,因为不存在什么查找会越界吧。如果是我理解错误麻烦大佬能指出orz

这里给出 fhqTreap 与 vector 的代码实现。

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

const int inf = 2100000000;
const int N = 300007;

template < class T > inline void read(T &x)
{
    x = 0; bool f = 1; register char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar())
        if(ch == '-') f = 0;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = (x << 1) + (x << 3) + (ch ^ 48);
    x = f ? x : -x;
}

int n, m;
int a[N], Ans[N];
int root, cnt;

struct fhqTreap
{
    int l, r;
    int val, key;
    int size;
};
fhqTreap tr[N << 1];

inline void pushUp(int p) {
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}

inline int newnode(int val)
{
    ++cnt; tr[cnt].l = tr[cnt].r = 0;
    tr[cnt].val = val, tr[cnt].key = rand();
    tr[cnt].size = 1; return cnt;
}

void split(int p, int val, int &x, int &y)
{
    if(!p)
    {
        x = y = 0;
        return ;
    }
    if(tr[p].val <= val)
    {
        x = p;
        split(tr[p].r, val, tr[p].r, y);
    }
    else
    {
        y = p;
        split(tr[p].l, val, x, tr[p].l);
    }
    pushUp(p);
}

int merge(int x, int y)
{
    if(!x || !y) return x | y;
    if(tr[x].key > tr[y].key)
    {
        tr[x].r = merge(tr[x].r, y);
        pushUp(x); return x;
    }
    else
    {
        tr[y].l = merge(x, tr[y].l);
        pushUp(y); return y;
    }
}

int kthNum(int p, int k)
{
    if(k <= tr[tr[p].l].size)
        return kthNum(tr[p].l, k);
    else if(k == tr[tr[p].l].size + 1)
        return p;
    else
    {
        k -= (tr[tr[p].l].size + 1);
        return kthNum(tr[p].r, k);
    }
}

//以上为 fhq-treap 板子

struct captainMo { int l, r, k, id, block; };
captainMo q[N];

inline bool cmp(captainMo a, captainMo b) {
    return (a.block ^ b.block) ? a.block < b.block : (a.block & 1) ? a.r < b.r : a.r > b.r;
}

//使用奇偶性排序加速,这里不细讲。

inline void del(int t)
{
    int val = a[t], x, y, z;
    split(root, val, x, y);
    split(x, val - 1, x, z);
    z = merge(tr[z].l, tr[z].r);
    root = merge(merge(x, z), y);
}

//树中删除下标为 t 的狗的颜值

inline void add(int t)
{
    int val = a[t], x, y;
    split(root, val, x, y);
    root = merge( merge(x, newnode(val)), y );
}

//添加下标为 t 的狗的颜值

signed main()
{
    srand(1******7);
    read(n); read(m);

    //块的大小设为 n/√(m*2/3) 玄学加速
    register int S = n / sqrt((m << 1) / 3);
    for(register int i = 1; i <= n; ++i) read(a[i]);
    for(register int i = 1; i <= m; ++i)
    {
        read(q[i].l), read(q[i].r), read(q[i].k);
        q[i].id = i, q[i].block = q[i].l / S;
    }
    sort(q + 1, q + m + 1, cmp);

    //莫队操作
    register int l = 1, r = 0;
    for(register int i = 1; i <= m; ++i)
    {
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(l < q[i].l) del(l++);
        while(r > q[i].r) del(r--);
        Ans[q[i].id] = tr[kthNum(root, q[i].k)].val;
        //记录此询问的位置的答案
    }
    for(register int i = 1; i <= m; ++i) printf("%d\n", Ans[i]);
    return 0;
}
#pr\
agma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;

const int inf = (1 << 30);
const int N = 300007;

template < class T > inline void read(T &x)
{
    x = 0; bool f = 1; register char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar())
        if(ch == '-') f = 0;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = (x << 1) + (x << 3) + (ch ^ 48);
    x = f ? x : -x;
}

int n, m;
int a[N], Ans[N];

vector < int > v;

struct captainMo { int l, r, k, id, block; };
captainMo q[N];

inline bool cmp(captainMo a, captainMo b) {
    return (a.block ^ b.block) ? a.block < b.block : (a.block & 1) ? a.r < b.r : a.r > b.r;
}

inline void del(int t) {
    v.erase(lower_bound(v.begin(), v.end(), a[t]));
}
inline void add(int t) {
    v.insert(lower_bound(v.begin(), v.end(), a[t]), a[t]);
}

signed main()
{
    read(n); read(m);
    v.push_back(inf); v.push_back(-inf);
    //这里是为了不 lower_bound 出界 RE

    register int S = n / sqrt((m << 1) / 3);
    for(register int i = 1; i <= n; ++i) read(a[i]);
    for(register int i = 1; i <= m; ++i)
    {
        read(q[i].l), read(q[i].r), read(q[i].k);
        q[i].id = i, q[i].block = q[i].l / S;
    }
    sort(q + 1, q + m + 1, cmp);

    register int l = 1, r = 0;
    for(register int i = 1; i <= m; ++i)
    {
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(l < q[i].l) del(l++);
        while(r > q[i].r) del(r--);
        Ans[q[i].id] = v.at(q[i].k + 1);
        //插入了-inf且不会被删除,所以排名+1
    }
    for(register int i = 1; i <= m; ++i) printf("%d\n", Ans[i]);
    return 0;
}