Luogu P1533 可怜的狗狗

题目链接：https://www.luogu.org/problemnew/show/P1533

没人写$fhq\ treap$做法，那我就补一篇qwq

看到这题第一时间想主席树，然后发现我还没学主席树，于是就写了平衡树做法（当然树状数组+二分的套路也是可以的，但是两个$log$的复杂度太优秀了就不写了）

其实和treap的写法差不多，也是排序一遍然后插入，删除，求$kth$

不过好写很多，主体就40+行，注意一开始那个节点的值一定要大...

我开$0x3f$然后挂了一个上午...

（其实一开始还写了莫队来着但是发现不需要）

#include <bits/stdc++.h>

#define ll long long

#define inf 0x7fffffff

#define il inline

namespace io {

    #define in(a) a=read()

    #define out(a) write(a)

    #define outn(a) out(a),putchar('\n')

    #define I_int int

    inline I_int read() {

        I_int x =  , f =  ; char c = getchar() ;

        while( c < '' || c > '' ) { if( c == '-' ) f = - ; c = getchar() ; }

        while( c >= '' && c <= '' ) { x = x *  + c - '' ; c = getchar() ; }

        return x * f ;

    }

    char F[  ] ;

    inline void write( I_int x ) {

        if( x ==  ) { putchar( '' ) ; return ; }

        I_int tmp = x >  ? x : -x ;

        if( x <  ) putchar( '-' ) ;

        int cnt =  ;

        while( tmp >  ) {

            F[ cnt ++ ] = tmp %  + '' ;

            tmp /=  ;

        }

        while( cnt >  ) putchar( F[ -- cnt ] ) ;

    }

    #undef I_int

}

using namespace io ;

using namespace std ;

#define N 300010

#define int long long

int n , tot = , root = ;

//fhq-treap

struct fhq_treap {

    int siz , val , lc , rc , rnk ;

} t[N] ;

void pushup(int rt) {t[rt].siz = t[t[rt].lc].siz + t[t[rt].rc].siz +  ;}

void split(int &a , int &b , int val , int rt) {

    if(!rt) { a = b =  ; return ; }

    if(t[rt].val <= val) a = rt , split(t[a].rc , b , val , t[rt].rc) ;

    else b = rt , split(a , t[b].lc , val , t[rt].lc) ;

    pushup(rt) ;

}

void merge(int a , int b , int &rt) {

    if(!a || !b) {rt = a + b ; return ;}

    if(t[a].rnk < t[b].rnk) rt = a , merge(t[a].rc , b , t[rt].rc) ;

    else rt = b , merge(a , t[b].lc , t[rt].lc) ;

    pushup(rt) ;

}

int new_node(int val) {

    t[++tot] = (fhq_treap) { , val ,  ,  , rand()} ;

    return tot ;

}

inline void insert(int val) {

    int x =  , y =  , z = new_node(val) ;

    split(x , y , val , root) ;

    merge(x , z , x) ; merge(x , y , root) ;

}

void Del(int val) {

    int x =  , y =  , z =  ;

    split(x , y , val , root) ; split(x , z , val -  , x) ;

    merge(t[z].lc , t[z].rc , z) ; merge(x , z , x) ; merge(x , y , root) ;

}

inline int find_val(int rnk , int rt) {

    while(t[t[rt].lc].siz +  != rnk) {

        if(t[t[rt].lc].siz >= rnk) rt = t[rt].lc ;

        else rnk -= t[t[rt].lc].siz +  , rt = t[rt].rc ;

    }

    return t[rt].val ;

}

//fhq-treap end

struct query {

    int l , r , val , id;

} q[N] ;

int ans[N] , a[N] , block ;

bool cmp(query a , query b) {

    return a.l == b.l ? a.r < b.r : a.l < b.l ;

}

signed main() {

#ifndef ONLINE_JUDGE

    freopen("1.in","r",stdin);

    freopen("1.out","w",stdout);

#endif

    srand((unsigned)time()) ;

    n = read() ; int m = read() ;

    new_node(inf) ; t[].siz =  ;

    for(int i =  ; i <= n ; i ++) a[i] = read() ;

    for(int i =  ; i <= m ; i ++) q[i] = (query) {read() , read() , read() , i} ;

    block = sqrt(n) ; sort(q +  , q + m +  , cmp) ;

    q[].l =  ;

    for(int i =  ; i <= m ; i ++) {

        for(int cur = q[i-].r +  ; cur <= q[i].r ; cur ++) insert(a[cur]) ;

        for(int cur = q[i-].l ; cur < q[i].l ; cur ++) Del(a[cur]) ;

        ans[q[i].id] = find_val(q[i].val , root) ;

    }

    for(int i =  ; i <= m ; i ++) outn(ans[i]) ;

}