主席树模板

主席树模板

题目描述

给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值

输入样例#1：

5 5 25957 6405 15770 26287 26465 2 2 1 3 4 1 4 5 1 1 2 2 4 4 1

输出样例#1：

6405 15770 26287 25957 26287

主席树模板

#include#define N 200005using namespace std;int a[N],b[N],rt[N];struct Node{int l,r,val;}t[N*20];int n,m,tot;int read(){ int cnt=0,f=1;char ch=0; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar(); return cnt*f;}void build(int &o,int l,int r){ o=++tot; if(l==r) return; int mid=(l+r)>>1; build(t[o].l,l,mid); build(t[o].r,mid+1,r);}void update(int &o,int l,int r,int last,int pos){ o=++tot; t[o].l=t[last].l,t[o].r=t[last].r; t[o].val=t[last].val+1; if(l==r) return; int mid=(l+r)>>1; if(pos<=mid) update(t[o].l,l,mid,t[last].l,pos); else update(t[o].r,mid+1,r,t[last].r,pos);}int quary(int L,int R,int l,int r,int k){ if(l==r) return l; int mid=(l+r)>>1; int cnt=t[t[R].l].val-t[t[L].l].val; if(k<=cnt) return quary(t[L].l,t[R].l,l,mid,k); else return quary(t[L].r,t[R].r,mid+1,r,k-cnt);}int main(){ int n=read(),m=read(); for(int i=1;i<=n;i++) a[i]=b[i]=read(); sort(b+1,b+n+1); int sz=unique(b+1,b+n+1)-(b+1); build(rt[0],1,sz); for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+sz+1,a[i])-b; for(int i=1;i<=n;i++) update(rt[i],1,sz,rt[i-1],a[i]); while(m--){ int x=read(),y=read(),k=read(); int ans=quary(rt[x-1],rt[y],1,sz,k); printf("%d\n",b[ans]); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。