主席树

主席树

小小总结：
1.

主席树静态区间第k小板子

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define rt 1,n,1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 2e5+10;
const int mod = 1e9+7;
const double eps = 1e-7;

int tot;
int a[maxn], b[maxn], T[maxn];
int sz[maxn<<5], L[maxn<<5], R[maxn<<5];

void build(int l, int r, int &now) {
    now=++tot;
    sz[now]=0;
    int m=(l+r)/2;
    if(l==r) return;
    build(l,m,L[now]), build(m+1,r,R[now]);
}

void update(int x, int l, int r, int pre, int &now) {
    now=++tot;
    L[now]=L[pre], R[now]=R[pre], sz[now]=sz[pre]+1;
    if(l==r) return;
    int m=(l+r)/2;
    if(x<=m) update(x,l,m,L[pre],L[now]);
    else update(x,m+1,r,R[pre],R[now]);
}

int qk(int k, int x, int y, int l, int r) {
    if(l==r) return l;
    int s=sz[L[y]]-sz[L[x]];
    int m=(l+r)/2;
    if(s>=k) return qk(k,L[x],L[y],l,m);
    else return qk(k-s,R[x],R[y],m+1,r);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int nn=unique(b+1,b+1+n)-b-1;
    tot=0, build(1,nn,T[0]);
    for(int i=1; i<=n; ++i) {
        int t=lower_bound(b+1,b+1+nn,a[i])-b;
        update(t,1,nn,T[i-1],T[i]);
    }
    while(q--) {
        int x, y, k;
        scanf("%d%d%d", &x, &y, &k);
        printf("%d\n", b[qk(k,T[x-1],T[y],1,nn)]);
    }
}