首页 > 代码库 > 主席树——求静态区间第k大
主席树——求静态区间第k大
例题:poj2104 http://poj.org/problem?id=2104
讲解:http://blog.sina.com.cn/s/blog_6022c4720102w03t.html
http://seter.is-programmer.com/posts/31907.html
刚刚根据以上2篇博客看懂,还没到写讲解的水平
#include<cstdio> #include<algorithm> using namespace std; const int N=100001; int l_child[N*18],r_child[N*18],sum[N*18]; int n,m,a[N],hash[N],cnt,root[N]; int x,y,k; void discrete() { sort(hash+1,hash+n+1); cnt=unique(hash+1,hash+n+1)-(hash+1); for(int i=1;i<=n;i++) a[i]=lower_bound(hash+1,hash+cnt+1,a[i])-hash; } int init() { int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘) {if(c==‘-‘) f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int query(int x,int y,int l,int r,int k) { if(l==r) return l; int mid=l+r>>1,tmp=sum[l_child[y]]-sum[l_child[x]]; if(tmp>=k) return query(l_child[x],l_child[y],l,mid,k); else return query(r_child[x],r_child[y],mid+1,r,k-tmp); } int tot=0; void build(int x,int &y,int l,int r,int v) { sum[y=++tot]=sum[x]+1; if(l==r) return; int mid=l+r>>1; if(v<=mid) { r_child[y]=r_child[x]; build(l_child[x],l_child[y],l,mid,v); } else { l_child[y]=l_child[x]; build(r_child[x],r_child[y],mid+1,r,v); } } int main() { n=init();m=init(); for(int i=1;i<=n;i++) a[i]=init(),hash[i]=a[i]; discrete(); //for(int i=1;i<=n;i++) printf("%d ",a[i]); for(int i=1;i<=n;i++) build(root[i-1],root[i],1,cnt,a[i]); for(int i=1;i<=m;i++) { x=init();y=init();k=init(); printf("%d\n",hash[query(root[x-1],root[y],1,cnt,k)]); } }
主席树——求静态区间第k大
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。