区间第k值

给定一个长度为n的序列A，有m个询问，每次询问下标在[L,R]范围内的数字，从小到大排序之后，第K小的元素值。

输入描述:

第一行两个整数n和m。
第二行n个整数，表示Ai。
接下来m行，每行3个整数L,R,K。

输出描述:

对于每个询问，输出相应的结果。

示例1
输入

5 3
10 5 3 4 8
1 2 1
2 4 3
1 5 4

输出

5
5
8

说明

n,m<=30000

qujiank_fenkuai.cppview raw

#include<bits/stdc++.h>
#define M 30005
using namespace std;
int A[M],B[M],S,num[M];
int sum[180][M];
int get(int L,int R,int x){//在[L,R]范围内找<=x的个数
    int kl=L/S,kr=R/S,cnt=0;
    if(kl==kr){
        for(int i=L;i<=R;i++)
            cnt+=A[i]<=num[x];
    }else{
        for(int i=L;i<(kl+1)*S;i++)cnt+=A[i]<=num[x];
        for(int i=kl+1;i<kr;i++)cnt+=sum[i][x];
        for(int i=kr*S;i<=R;i++)cnt+=A[i]<=num[x];
    }
    return cnt;
}
int main(){

    freopen("kth.in","r",stdin);
    freopen("my.out","w",stdout);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        num[i-1]=B[i]=A[i];
    }
    S=sqrt(n);
    sort(num,num+n);
    int v=unique(num,num+n)-num;
    for(int i=1;i<=n;i++){
        int k=lower_bound(num,num+v,A[i])-num;
        sum[i/S][k]++;
    }
    for(int i=1;i<=n/S;i++)//预处理每个块的前缀和
        for(int j=1;j<v;j++)sum[i][j]+=sum[i][j-1];

    while(m--){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        int L=0,R=v-1,res;
        while(L<=R){
            int mid=(L+R)>>1;
            int tmp=get(a,b,mid);
            if(tmp>=c){
                res=mid;R=mid-1;
            }else L=mid+1;
        }
        printf("%d\n",num[res]);
    }
    return 0;
}

qujiank_fenkuai1.cppview raw

#include<bits/stdc++.h>
#define M 30005
using namespace std;
int A[M],B[M],S,num[M];
int get(int L,int R,int x){//在[L,R]范围内找<=x的个数
    int kl=L/S,kr=R/S,cnt=0;
    if(kl==kr){
        for(int i=L;i<=R;i++)
            cnt+=A[i]<=x;
    }else{
        for(int i=L;i<(kl+1)*S;i++)cnt+=A[i]<=x;
        for(int i=kl+1;i<kr;i++)cnt+=upper_bound(B+i*S,B+i*S+S,x)-(B+i*S);
        for(int i=kr*S;i<=R;i++)cnt+=A[i]<=x;
    }
    return cnt;
}
int main(){
    freopen("kth.in","r",stdin);
    freopen("my.out","w",stdout);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        num[i]=B[i]=A[i];
    }
    S=sqrt(n*log(n)/log(2));
    for(int i=S;i+S-1<=n;i+=S)sort(B+i,B+i+S); //第一个区间不排序
    sort(num+1,num+n+1);
    while(m--){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        int L=1,R=n,res;
        while(L<=R){
            int mid=(L+R)>>1;
            int tmp=get(a,b,num[mid]);
            if(tmp>=c){
                res=num[mid];
                R=mid-1;
            }else L=mid+1;
        }
        printf("%d\n",res);
    }
    return 0;
}

qujiank_segtree.cppview raw

#include<bits/stdc++.h>
#define M 30005
using namespace std;
struct node{
    int L,R;
    vector<int>num;
}tree[M<<2];
int A[M],s[M];
void build(int L,int R,int p){
    tree[p].L=L,tree[p].R=R;
    tree[p].num.clear();
    if(L==R){
        tree[p].num.push_back(A[L]);
        return;
    }
    int mid=(L+R)>>1;
    build(L,mid,p<<1);
    build(mid+1,R,p<<1|1);
    tree[p].num.resize(R-L+1);//****
    merge(tree[p<<1].num.begin(),tree[p<<1].num.end(),
          tree[p<<1|1].num.begin(),tree[p<<1|1].num.end(),
          tree[p].num.begin());
}
int query(int L,int R,int x,int p){
    if(L==tree[p].L&&R==tree[p].R){
        return upper_bound(tree[p].num.begin(),tree[p].num.end(),x)-tree[p].num.begin();
    }
    int mid=(tree[p].L+tree[p].R)>>1;
    if(R<=mid)return query(L,R,x,p<<1);
    else if(L>mid)return query(L,R,x,p<<1|1);
    else{
        return query(L,mid,x,p<<1)+query(mid+1,R,x,p<<1|1);
    }
}
int main(){
    freopen("kth.in","r",stdin);
    freopen("my.out","w",stdout);
    int n,m,a,b,c;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&A[i]);
        s[i-1]=A[i];
    }
    sort(s,s+n);
    build(1,n,1);

    while(m--){
        scanf("%d %d %d",&a,&b,&c);
        int L=0,R=n-1,res;
        while(L<=R){
            int mid=(L+R)>>1;
            int tmp=query(a,b,s[mid],1);
            if(tmp>=c){
                R=mid-1;res=s[mid];
            }else L=mid+1;
        }
        printf("%d\n",res);
    }
    return 0;
}

qujiank_bitree.cppview raw

#include<bits/stdc++.h>
#define M 30005
#define lowbit(x) (x&(-x))
using namespace std;
int A[M],B[M],S,num[M],C[M],V,ans[M],n;
struct node{
    int a,b,c,l,r,mid,res,id;
}query[M];
struct Num{
    int id,x;
}G[M];
bool cmp(node a,node b){
    return a.mid<b.mid;
}
bool cmp1(Num a,Num b){
    return a.x<b.x;
}
void Add(int x){
    if(x==0)return;
    while(x<=n){
        C[x]++;x+=lowbit(x);
    }
}
int Get(int x){
    int res=0;
    while(x>0){
        res+=C[x];
        x-=lowbit(x);
    }
    return res;
}
int main(){
    freopen("kth.in","r",stdin);
    freopen("my.out","w",stdout);
    int m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
        num[i]=A[i];
    }
    sort(num,num+n);
    V=unique(num,num+n)-num;
    for(int i=0;i<n;i++){
        A[i]=lower_bound(num,num+V,A[i])-num;
        G[i].id=i+1,G[i].x=A[i];
    }
    sort(G,G+n,cmp1);
    int a,b,c;
    for(int i=0;i<m;i++){
        scanf("%d %d %d",&a,&b,&c);
        query[i]=(node){a,b,c,0,V-1,(V-1)>>1,-1,i};
    }
    for(int i=0;i<15;i++){
        sort(query,query+m,cmp);

        int k=0;
        for(int j=1;j<=n;j++)C[j]=0;
        for(int j=0;j<m;j++){
            if(query[j].l>query[j].r)continue;
            while(k<n&&G[k].x<=query[j].mid){
                Add(G[k++].id);
            }
            int tmp=Get(query[j].b)-Get(query[j].a-1);
            if(tmp>=query[j].c){
                query[j].res=query[j].mid;
                query[j].r=query[j].mid-1;
            }else{
                query[j].l=query[j].mid+1;
            }
            query[j].mid=query[j].l+query[j].r>>1;
        }
    }
    for(int i=0;i<m;i++)ans[query[i].id]=num[query[i].res];
    for(int i=0;i<m;i++)printf("%d\n",ans[i]);
    return 0;
}