[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;
}