首页 > 代码库 > poj_2104: K-th Number 【主席树】
poj_2104: K-th Number 【主席树】
题目链接
学习了一下主席树,感觉具体算法思路不大好讲。。
大概是先建个空线段树,然后类似于递推,每一个都在前一个“历史版本”的基础上建立一个新的“历史版本”,每个历史版本只需占用树高个空间(好神奇!)
查询时这道题是通过“历史版本”间作差解决
*另外提一下,在建立“历史版本”的过程中,是“新建”,而不是“更新”,是先copy过来原有的,再按个人需求改成自己的,所产生的一个新的“历史版本”
希望注释能有帮助
//吐槽一下,本人看kuangbin模板看得好费劲,一方面不习惯用lson[],rson[]数组搞线段树,另一方面他的update query函数都是用二分写的,看半天没理解。。。
以下是按个人习惯加了注释的代码
#include<cstdio> #include<queue> #include<algorithm> #include<cstdlib> #include<cstring> #include<iostream> #include<cmath> #define M 100000+5 using namespace std; const int N=1e5+7; const int INF=0x3f3f3f3f; struct node { int l,r; //l,r分别指向左右孩子,但由于历史的错乱,二者的值未必有规律 int size; //当前历史版本里,该节点中所包含的元素个数 //p.s. 在最后一个历史版本里,size即为总元素个数n }tr[N*20]; //主席树的初始状态为一“空架子” //每次updata都在前一“历史版本”基础上新建h个结点,共updata n次,产生了n个历史版本,每个版本占用空间为h*sizeof(one node) int tot; //结点建立顺序|所赋标号 int n; //共n个数 int a[N]; //读入数组 int root[N];//记录a[]中每一个数对应各“历史版本”在主席树中的根结点标号 int m; //t[]中元素个数 int t[N]; //离散数组 int pos(int x) { return lower_bound(t+1,t+1+m,x)-t; } int q; //q个询问 int build(int l,int r) { int rt=tot++; tr[rt].size=0; if(l==r) return rt; int mid=(l+r)>>1; tr[rt].l=build(l,mid); tr[rt].r=build(mid+1,r); return rt; } // pre_node:最近一历史,[l,r]当前所更新到的包含x的区间 // x此次更新的“终点” // 沿途要增加的“权值” // p.s. 1<=l<=r<=m int updata(int pre_node,int l,int r,int x,int v) { int rt=tot++; //rt为新结点的标号 tr[rt]=tr[pre_node]; //先拷贝原指向当前区间的结点 tr[rt].size+=v; // 在函数不断向下深入过程中,更新node.size if(l==r) return rt; int mid=(l+r)>>1; if(x<=mid) tr[rt].l=updata(tr[pre_node].l,l,mid,x,v); else tr[rt].r=updata(tr[pre_node].r,mid+1,r,x,v); return rt; // 在函数逐步return过程中,更新node.l|r } // ql,qr反应的是在a[]中的下标,对应着更新到该下标时的“历史版本” // l,r反应的是在t[]中的下标 int query(int ql,int qr,int l,int r,int k) { if(l==r) return l; int diff=tr[tr[qr].l].size-tr[tr[ql].l].size;//在更新到ql位置和更新到qr位置时两个“历史版本”下左孩子的size之差 // p.s. size的大小反应较小数的多少 int mid=(l+r)>>1; if(diff>=k) return query(tr[ql].l,tr[qr].l,l,mid,k); else return query(tr[ql].r,tr[qr].r,mid+1,r,k-diff); } int main() { while(~scanf("%d%d",&n,&q)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]),t[i]=a[i]; sort(t+1,t+1+n); m=unique(t+1,t+1+n)-t-1; m++,t[m]=INF; tot=0; root[0]=build(1,m); //初始化一个空线段树 for(int i=1;i<=n;i++) { int order=pos(a[i]); root[i]=updata(root[i-1],1,m,order,1); //每次在上一次已完成的基础上新增h个结点 //从根 逐步新建结点到 a[i]在线段树上所对应的位置 //在这个逐步新建结点的过程中,要新建的结点的l,r始终满足l<=m<=r //这些结点每一个的size都在pre_node的基础上+1 } while(q--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",t[query(root[l-1],root[r],1,m,k)]); } } }
poj_2104: K-th Number 【主席树】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。