luoguP1533 可怜的狗狗 平衡树模板题

#include <bits/stdc++.h>   
#define ll long long 
#define N 300200  
#define lson s[x].ch[0] 
#define rson s[x].ch[1]     
#define inf 21000000000000
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;    
int n,m,tot,root;
ll a[N],Ans[N];      
struct data {
    int ch[2],f,si; 
    ll v;     
}s[N];  
struct que { 
    int x,y,id,kth;  
    bool operator<(const que b) const { 
        return x<b.x;    
    }      
}q[N];  
int get(int x) { return s[s[x].f].ch[1]==x; }   
void pushup(int x) { s[x].si=s[lson].si+s[rson].si+1; }
void rotate(int x) 
{
    int old=s[x].f,fold=s[old].f,which=get(x); 
    s[old].ch[which]=s[x].ch[which^1];  
    if(s[old].ch[which]) s[s[old].ch[which]].f=old;  
    s[x].ch[which^1]=old,s[old].f=x,s[x].f=fold;  
    if(fold) s[fold].ch[s[fold].ch[1]==old]=x;  
    pushup(old),pushup(x);   
}
void splay(int x,int &tar) 
{
    for(int u=s[tar].f,fa;(fa=s[x].f)!=u;rotate(x))  
        if(s[fa].f!=u) rotate(get(fa)==get(x)?fa:x);  
    tar=x;   
}
int find(int x,int kth) 
{
    if(s[lson].si+1==kth) return x;  
    else
    {
        if(kth<=s[lson].si) return find(lson,kth);  
        else return find(rson,kth-s[lson].si-1);  
    }
}  
int getnum(int x,ll v)   
{
    if(s[x].v==v) return x;   
    else return getnum(s[x].ch[v>s[x].v],v);     
}   
void ins(int &x,int ff,ll v) 
{
    if(!x) x=++tot,s[x].f=ff,s[x].v=v;  
    else ins(s[x].ch[v>s[x].v],x,v);   
    pushup(x);   
}    
// 删掉前 size 个      
void del(ll v) 
{    
    int x=getnum(root,v);     
    splay(x,root);     
    int l=s[root].ch[0],r=s[root].ch[1];      
    while(s[l].ch[1]) l=s[l].ch[1];     
    splay(l,s[root].ch[0]);     
    s[r].f=l,s[l].ch[1]=r,s[l].f=0,root=l,pushup(l);    
}  
int main() 
{ 
    // setIO("input");    
    // freopen("input.out","w",stdout);         
    scanf("%d%d",&n,&m);   
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);  
    for(int i=1;i<=m;++i) scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].kth),q[i].id=i; 
    sort(q+1,q+1+m);           
    ins(root,0,-inf);       // tot=1
    ins(root,0,inf);        // tot=2      
    int l=1,r=0;          
    for(int i=1;i<=m;++i) 
    {      
        while(r<q[i].y) ins(root,0,a[++r]);         
        while(l<q[i].x) del(a[l++]);                         
        int x=find(root,q[i].kth+1);     
        Ans[q[i].id]=s[x].v;    
    }
    for(int i=1;i<=m;++i) printf("%lld\n",Ans[i]);   
    return 0; 
}