区间k小值（可持久化线段树）

题目描述
给定一个序列\(a_1,a_2,\dots,a_n\)，\(m\)次操作，每次给定\(l,r,k\)，问\(a_l,a_{l+1},\dots,a_r\)中第\(k\)小的值。
输入
第一行一个正整数\(T(1\leq T\leq 3)\)，表示测试数据的数量。

每组数据第一行\(n,m(1\leq n,m\leq 100000)\)。

第二行\(n\)个正整数\(a_1,a_2,\dots,a_n(1\leq a_i\leq n)\)。

接下来\(m\)行，每行描述一个操作，其中\(1\leq l\leq r\leq n,1\leq k\leq r-l+1\)。
输出
对于每个询问，输出一行一个整数，即第\(k\)小的值。
样例输入 Copy
1
5 5
1 3 5 4 2
1 3 3
2 4 2
1 5 2
4 4 1
3 5 1
样例输出 Copy
5
4
2
4
2

考虑二分答案ans在[l,r]上的<=ans的数和k的关系，用f[i][j]表示前i个数里j出现的次数，通过可持久化将j作为线段树的点

然后考虑线段树上二分去掉一个log

注意不能build,否则会超时，原因尚不明确

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e5+10,M = 2e6;
//T[i]里保存的是i号线段树的根节点标号,l,r,val要开到nlogn
int a[N],T[N],l[M],r[M],val[M];
int n,m,tot;
inline void pushup(int p)
{
    val[p] = val[l[p]] + val[r[p]];
}

//对根为x的线段树区间[a,b]里的c点修改d
//注意change里的左右节点编号
int change(int x,int a,int b,int c,int d)
{
    int y = ++tot;
    if(a==b)
    {
        val[y] = val[x] + d;
        return y;
    }
    int M = (a+b)/2;
    if(c<=M) 
    {
        l[y] = change(l[x],a,M,c,d);
        r[y] = r[x];
    }
    else
    {
        l[y] = l[x];
        r[y] = change(r[x],M+1,b,c,d); 
    }
    pushup(y);
    //if(a==4&&b==4) cout<<l[y]<<' '<<r[y]<<'\n';
    return y;
}
//对根为x当前区间为[a,b]的线段树查询区间[ql,qr]
int query(int x,int a,int b,int ql,int qr)
{
    if(ql==a&&b==qr) return val[x];
     
    int m = (a+b)/2;
    //注意此处的修改用ql,qr表示询问区间
    if(qr<=m) return query(l[x],a,m,ql,qr);
    else if(ql>m) return query(r[x],m+1,b,ql,qr);
    else return query(l[x],a,m,ql,m)+query(r[x],m+1,b,m+1,qr);
}
//check(x)计算的是[l,r]中小于等于x的数字个数
//注意调用query时使用的是T数组里的标号
inline int ask(int x,int y,int k)
{
    int a = 1,b = n;
    while(a < b)
    {
        int m = (a+b)/2;
        int t = val[l[y]] - val[l[x]];
        if(t >= k) x = l[x],y = l[y],b = m;
        else //注意若在右半边需要把k-=t
        k -= t, x = r[x], y = r[y], a = m+1;
    }
    return a;
}
void solve()
{
    tot = 0;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    
    // T[0] = 1;
    // build(1,n);
     
    for(int i=1;i<=n;++i) T[i] = change(T[i-1],1,n,a[i],1);
     
    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<ask(T[l-1],T[r],k)<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}