R19436221 区间第k小 主席树

本站寻求有缘人接手，详细了解请联系站长QQ1493399855

主席树模板题，记录一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int root[maxn],t,d;
int a[maxn],b[maxn];
struct node
{int l,r,cnt;
}tree[maxn*100];
void insert(int &now,int pre,int l,int r,int x)
{now=++t;tree[now]=tree[pre];tree[now].cnt++;if(l==r) return;int mid=(l+r)>>1;if(x<=mid) insert(tree[now].l,tree[pre].l,l,mid,x);else insert(tree[now].r,tree[pre].r,mid+1,r,x);
}
int query(int st,int ed,int l,int r,int k)
{if(l==r) return l;int mid=(l+r)>>1;int x=tree[tree[ed].l].cnt-tree[tree[st].l].cnt;if(k<=x) return query(tree[st].l,tree[ed].l,l,mid,k);else return query(tree[st].r,tree[ed].r,mid+1,r,k-x);
}
int main()
{int n,m,l,r,k;cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}sort(b+1,b+1+n);d=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++){int x=lower_bound(b+1,b+1+d,a[i])-b;insert(root[i],root[i-1],1,d,x);}while(m--){scanf("%d %d %d",&l,&r,&k);printf("%d
",b[query(root[l-1],root[r],1,d,k)]);}
}