首页 > 代码库 > 【BZOJ2733】永无乡[splay启发式合并or线段树合并]
【BZOJ2733】永无乡[splay启发式合并or线段树合并]
题目大意：给你一些点，修改是在在两个点之间连一条无向边，查询时求某个点能走到的点中重要度第k大的点。题目中给定的是每个节点的排名，所以实际上是求第k小；题目求的是编号，不是重要度的排名。我一开始差点被这坑了。
网址：http://www.lydsy.com/JudgeOnline/problem.php?id=2733
这道题似乎挺经典的（至少我看许多神犇很早就做了这道题）。这道题有两种写法：并查集+（splay启发式合并or线段树合并）。我写的是线段树合并，因为……splay不会打+懒得学。
线段树合并具体可以看ppt：https://wenku.baidu.com/view/88f4e134e518964bcf847c95.html（线段树的合并——杭州二中黄嘉泰）
这道题可以一开始每个节点建一棵值域线段树（没用到的子树像trie一样，先指向null），然后合并操作就用上面文章中线段树合并的方法，同时把并查集合并一下（如果把树x合并到树y，那么在并查集里也要把fa[x]改为y，这样就能保证并查集的根和线段树的根是同一个节点），查询可以先用并查集查出这个节点属于哪棵树，然后在树上二分（就是在值域线段树上求序列第k大），然后就完了。
P.S.似乎不加读入优化我的线段树合并要比我一位同学的splay快400ms+，不过splay很常用，还是过几天学一学吧。。。（第一行是我加了快读的线段树合并，第二行没有加快读，第三行是同学的splay）
奇丑无比的代码：
#include<cstdio> using namespace std; struct hh{ int lc,rc,sum; }a[3000010]; int rank[100010],id[100010],fa[100010],tot; int read() { char c=getchar(),flag=1; while(c<‘0‘||‘9‘<c){ if(c==‘-‘)flag=-1; c=getchar(); } int tmp=0; while(‘0‘<=c&&c<=‘9‘){ tmp=tmp*10+c-‘0‘; c=getchar(); } return tmp*flag; } void add(int now,int x,int l,int r) { ++a[now].sum; if(l==r)return; if(x<=(l+r)>>1){ if(!a[now].lc)a[now].lc=++tot; add(a[now].lc,x,l,(l+r)>>1); } else{ if(!a[now].rc)a[now].rc=++tot; add(a[now].rc,x,((l+r)>>1)+1,r); } } int query(int now,int x,int l,int r) { if(l==r)return l; if(a[a[now].lc].sum>=x)return query(a[now].lc,x,l,(l+r)>>1); else return query(a[now].rc,x-a[a[now].lc].sum,((l+r)>>1)+1,r); } void merge(int x,int y) { a[x].sum+=a[y].sum; if(a[x].lc||a[x].rc){ if(a[y].lc){ if(!a[x].lc)a[x].lc=a[y].lc; else merge(a[x].lc,a[y].lc); } if(a[y].rc){ if(!a[x].rc)a[x].rc=a[y].rc; else merge(a[x].rc,a[y].rc); } } } int find(int x) { if(fa[x]==x)return x; return fa[x]=find(fa[x]); } int main() { int n=read(),m=read(),i; tot=n; for(i=1;i<=n;i++){ rank[i]=read(); id[rank[i]]=fa[i]=i; add(i,rank[i],1,n); } for(i=1;i<=m;i++){ int x=read(),y=read(),fx,fy; fx=find(x); fy=find(y); if(fx!=fy){ fa[fy]=fx; merge(fx,fy); } } m=read(); for(i=1;i<=m;i++){ char ch; scanf("%s",&ch); int x=read(),y=read(); if(ch==‘Q‘){ int fx=find(x); if(a[fx].sum<y)printf("-1\n"); else printf("%d\n",id[query(fx,y,1,n)]); } else{ int fx=find(x),fy=find(y); if(fx!=fy){ fa[fy]=fx; merge(fx,fy); } } } }
splay的等学了再补吧。。。
【BZOJ2733】永无乡[splay启发式合并or线段树合并]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。