主席树

主席树

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define NN 101000

int n,m,i,ord[NN],b[NN],totn,tott,root[NN],a,bb,c;

struct segtree{
    int ls,rs,l,r,w;
}t[NN*20];

int bsch(int x,int l,int r){
    int mid;
    while(l<=r){
       mid=(l+r)>>1;
       if (x==b[mid]) return mid;
       else if(b[mid]>x) r=mid-1;
       else l=mid+1;
    }
    printf("fuck!\n");
}

int build(int l,int r){
    int now=++tott;
    t[now].l=l;t[now].r=r;t[now].w=0;
    if (l==r){
        t[now].ls=t[now].rs=0;return now;
    }
    int mid=(l+r)>>1;
    t[now].ls=build(l,mid);
    t[now].rs=build(mid+1,r);
    return now;
}

int insert(int pos,int num,int pas){
    int now=++tott;
    t[now]=t[pas];
    t[now].w+=num;
    if (t[now].ls==t[now].rs) return now;
    int mid=(t[now].l+t[now].r)>>1;
    if (pos<=mid) t[now].ls=insert(pos,num,t[now].ls);
    else t[now].rs=insert(pos,num,t[now].rs);
    return now;
}

int query(int k,int t1,int t2){
     if (t[t1].l==t[t1].r) return t[t1].l;
     int tmp;
     if ((tmp=t[t[t2].ls].w-t[t[t1].ls].w)>=k){
        return query(k,t[t1].ls,t[t2].ls);
     }
     else {
        return query(k-tmp,t[t1].rs,t[t2].rs);
     }
}

inline bool cmp(int x,int y){return x<y;}

int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){scanf("%d",&ord[i]);b[i]=ord[i];}
    sort(b+1,b+n+1,cmp);
    totn=1;
    for(i=2;i<=n;i++){if (b[i]!=b[i-1]) b[++totn]=b[i];}
    for(i=1;i<=n;i++){ord[i]=bsch(ord[i],1,totn);}
    
    tott=0;
    root[0]=build(1,totn);
    for(i=1;i<=n;i++){
        root[i]=insert(ord[i],1,root[i-1]);
    }
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&bb,&c);
        printf("%d\n",b[query(c,root[a-1],root[bb])]);
    }
    return 0;
}