首页 > 代码库 > COGS 930. [河南省队2012] 找第k小的数 主席树
COGS 930. [河南省队2012] 找第k小的数 主席树
主席树裸板子
#include<cstdio> #include<iostream> #include<algorithm> #define MAXN 100005 #define MAX 2000005 using namespace std; int sum[MAX],l[MAX],mid[MAX],r[MAX],a[MAXN],b[MAXN],n,m,sz,size,root[MAXN],cnt; void build(int &x,int z,int y) { x=++sz; if(z==y){mid[sz]=-y;return;} mid[sz]=(z+y)>>1; build(l[x],z,mid[x]); build(r[x],mid[x]+1,y); } void update(int &x,int last,int to) { x=++sz; mid[sz]=mid[last]; sum[sz]=sum[last]+1; if(mid[sz]<0)return; l[sz]=l[last]; r[sz]=r[last]; if(to<=mid[x])update(l[x],l[last],to); else update(r[x],r[last],to); } int query(int x,int y,int k) { if(mid[y]<0)return b[-mid[y]]; cnt=sum[l[y]]-sum[l[x]]; if(k<=cnt)return query(l[x],l[y],k); else return query(r[x],r[y],k-cnt); } inline void work() { int x,y,k; scanf("%d%d%d",&x,&y,&k); printf("%d\n",query(root[x-1],root[y],k)); } int main() { freopen("kth.in","r",stdin); freopen("kth.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];} sort(b+1,b+n+1); size=unique(b+1,b+n+1)-(b+1); build(root[0],1,size); for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+size+1,a[i])-b;update(root[i],root[i-1],a[i]);} while(m--)work(); return 0; }
COGS 930. [河南省队2012] 找第k小的数 主席树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。