首页 > 代码库 > POJ2104 K-th Number（主席树）
POJ2104 K-th Number（主席树）
题意：
静态区间第K大
思路：
之前学划分树的时候当了模版练了，
感觉划分树真是不该学。。
又拿来练主席树吧
/* ***********************************************Author :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <cmath>#include <stdlib.h>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=1e5+10;const int M=N*30;int n,q,m,tot;int a[N],t[N],T[N],ls[M],rs[M],c[M];void init(){ for(int i=1;i<=n;i++) t[i]=a[i]; sort(t+1,t+1+n); m=unique(t+1,t+1+n)-t-1;}int build(int l,int r){ int node=tot++; c[node]=0; if(l!=r) { int mid=(l+r)>>1; ls[node]=build(l,mid); rs[node]=build(mid+1,r); } return node;}int update(int node,int pos,int val){ int newnode=tot++,tmp=newnode; c[newnode]=c[node]+val; int l=1,r=m; while(l<r) { int mid=(l+r)>>1; if(pos<=mid) { ls[newnode]=tot++; rs[newnode]=rs[node]; newnode=ls[newnode]; node=ls[node]; r=mid; } else { rs[newnode]=tot++; ls[newnode]=ls[node]; newnode=rs[newnode]; node=rs[node]; l=mid+1; } c[newnode]=c[node]+val; } return tmp;}int query(int lnode,int rnode,int k){ int l=1,r=m; while(l<r) { int mid=(l+r)>>1; if(c[ls[lnode]]-c[ls[rnode]]>=k) { r=mid; lnode=ls[lnode]; rnode=ls[rnode]; } else { l=mid+1; k-=c[ls[lnode]]-c[ls[rnode]]; lnode=rs[lnode]; rnode=rs[rnode]; } } return l;}int main(){ //freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&q)) { tot=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); init(); T[n+1]=build(1,m); for(int i=n;i;i--) { int pos=lower_bound(t+1,t+m+1,a[i])-t; T[i]=update(T[i+1],pos,1); } while(q--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",t[query(T[l],T[r+1],k)]); } } return 0;}
POJ2104 K-th Number（主席树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。