dc_y's Blog

总算会写主席树了好开桑~

题目描述

输入

输出

样例输入

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

样例输出

5
6
3

对每个前缀建一棵线段树，然后寻找第k个数就可以辣

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 101000
#define ls(i) T[(i)].ls
#define rs(i) T[(i)].rs
#define w(i) T[(i)].w
struct  node{
    int ls,rs,w;
    node(){ls=0;rs=0;w=0;}
}T[N*20];
int id,n,m,k,t,ans,x,y,z;
int f[N],a[N],b[N],root[N],p[N];
int cmp(int i,int j){
    return a[i]<a[j];
}
void add(int &i,int l,int r,int x){
    T[++id]=T[i];i=id;
    w(i)++;
    if (l==r) return;
    int mid=(l+r)/2;
    if (x<=mid) add(ls(i),l,mid,x);
    else add(rs(i),mid+1,r,x);
}
int find(int x,int y,int l,int r,int k){
    if (l==r) return(l);
    int mid=(l+r)/2;
    int s=w(ls(y))-w(ls(x));
    if (s>=k) return(find(ls(x),ls(y),l,mid,k));
    else return(find(rs(x),rs(y),mid+1,r,k-s));
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) {scanf("%d",&a[i]);p[i]=i;}
    sort(p+1,p+n+1,cmp);
    for (int i=1;i<=n;i++) b[p[i]]=i;
    for (int i=1;i<=n;i++){
        root[i]=root[i-1];
        add(root[i],1,n,b[i]);
    }
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        ans=find(root[x-1],root[y],1,n,z);
        printf("%d\n",a[p[ans]]);
    }
}