[LuoguP3834]主席树模板题 静态区间K大

[LuoguP3834]主席树模板题 静态区间K大

啊 我爱数据结构(迫真 其实马上快要写吐了呜呜呜呜呜
就当作回忆一下主席树怎么写吧哈哈哈哈哈 指针 永远滴神

#include<bits/stdc++.h>
#define maxn 200005
#define mid ((l+r)>>1)
using namespace std;
int n,q,a[maxn],z[maxn];
struct tree;
tree*NUL;
struct tree{
    int sum;
    tree *so[2];
    tree(){
        so[0]=so[1]=NUL;
        sum=0;
    }
    void update(){sum=so[0]->sum+so[1]->sum;}
    void build(tree *lst,int c,int l,int r){
        if(l==r) {sum=lst->sum+1;return;}
        bool b=(c>mid);
        int lx=(b?mid+1:l),rx=(b?r:mid);
        so[b^1]=lst->so[b^1];
        (so[b]=new tree)->build(lst->so[b],c,lx,rx);
        update();
    }
    int qry(tree *lst,int k,int l,int r)
    {
        if(l==r) return l;
        int tmp=so[0]->sum-lst->so[0]->sum;
        if(k<=tmp) so[0]->qry(lst->so[0],k,l,mid);
        else so[1]->qry(lst->so[1],k-tmp,mid+1,r);
    }
}*rt[maxn];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
    scanf("%d",&a[i]),z[i]=a[i];
    sort(z+1,z+n+1);
    for(int i=1;i<=n;++i)
    a[i]=lower_bound(z+1,z+n+1,a[i])-z;
    NUL=new tree;NUL->so[0]=NUL->so[1]=NUL;
    rt[0]=new tree;
    for(int i=1;i<=n;++i)
    (rt[i]=new tree)->build(rt[i-1],a[i],1,n);
    while(q--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",z[rt[r]->qry(rt[l-1],k,1,n)]);
    }
    return 0;
}

留下回复