主席树应用之一：区间第k大，中间还有用到vector离散化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=2e5+10;
vector<int>v;
typedef struct A{
    int l,r,sum;
    //l为一个离散化变量的左边界，r为右边界，都是对于值域而言的，sum存储数值在[l,r]区间内的数的个数 
}node;
node tree[maxn*20];
inline int getid(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1; 
}
inline int read(){
    int a=0,po=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') po=-1,ch=getchar();
    while (isdigit(ch)) a=a*10+ch-'0',ch=getchar();
    return a*po; 
}
int n,m,a[maxn],root[maxn],cnt;//n,m如题意所示，a为原数组，cnt为已分配节点数量 
inline void insert(int l,int r,int pre,int &now,int p){
    tree[++cnt]=tree[pre];
    now=cnt;
    tree[now].sum++;
    if(l==r)return;
    int m=l+r>>1;
    if(p<=m)insert(l,m,tree[pre].l,tree[now].l,p);
    else insert(m+1,r,tree[pre].r,tree[now].r,p);
}
int query(int l,int r,int start,int end,int k){
    if(l==r)return l;
    int m=l+r>>1;
    int tmp=tree[tree[end].l].sum-tree[tree[start].l].sum;
    if(k<=tmp)return query(l,m,tree[start].l,tree[end].l,k);
    else return query(m+1,r,tree[start].r,tree[end].r,k-tmp);
}
int main(){
     n=read(),m=read();
    for(int i=1;i<=n;i++)
        v.push_back(a[i]=read());
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++){
        insert(1,v.size(),root[i-1],root[i],getid(a[i]));
    }
    int l,r,k;
    
    while(m--){
        l=read(),r=read(),k=read();
        cout<<v[query(1,v.size(),root[l-1],root[r],k)-1]<<endl;
    }
    return 0;
}