BZOJ 3545 [ONTAK2010]Peaks Treap启发式合并

题意: 有n座山峰。m条双向道路。 每座山峰有高度。 每条路有一个困难值。 多次询问从一个山峰出发，经过道路的最大困难值不超过x能达到的第k高的山峰。 解析: 因为允许离线，所以我们可以把所有的边按照困难值排序，再把所有的询问按照困难值排序。 然后我们就可以搞一个双指针(似乎都这么叫)的东西来搞这道题。 那么每一次，我们要查某个山峰可以到达的山峰中第k高的。 因为困难值单调，所以我们可以考虑把每一个山峰看作一个平衡树，然后每一次就是合并两棵平衡树而已。 既然这么想了，我们肯定不能暴力合并，那样复杂度爆炸。 那启发式合并能不能过呢? 复杂度O（m*log^2(n)）发现可过。 所以就这样写了。 为了方便实现我们可以搞一个并查集来维护哪些山峰在一块。 代码:

using namespace std;int n,m,q;int val[N];int root[N];int tot,tot2;struct Line{int from,to,val;}l[M];struct node{int v,siz,l,r,rnd;}tr[N];struct query{int v,x,k,no;}que[M];void pushup(int rt){tr[rt].siz=tr[tr[rt].l].siz+1+tr[tr[rt].r].siz;}void lturn(int &rt){int t=tr[rt].r;tr[rt].r=tr[t].l;tr[t].l=rt;tr[t].siz=tr[rt].siz;pushup(rt);rt=t;}void rturn(int &rt){int t=tr[rt].l;tr[rt].l=tr[t].r;tr[t].r=rt;tr[t].siz=tr[rt].siz;pushup(rt);rt=t;}void insert(int &rt,int v,int no){if(!rt){rt=no;tr[rt].v=v,tr[rt].l=tr[rt].r=0;tr[rt].siz=1,tr[rt].rnd=rand();return;}tr[rt].siz++;if(v<tr[rt].v){insert(tr[rt].l,v,no);if(tr[tr[rt].l].rnd<tr[rt].rnd)rturn(rt);}else{insert(tr[rt].r,v,no);if(tr[tr[rt].r].rnd<tr[rt].rnd)lturn(rt);}}void merge(int x,int &y){if(!x)return;merge(tr[x].l,y);merge(tr[x].r,y);insert(y,tr[x].v,x);}int Query_rnk(int rt,int k){if(tr[rt].siz<k)return -1;if(tr[tr[rt].r].siz+1==k)return tr[rt].v;if(tr[tr[rt].r].siz+1>k)return Query_rnk(tr[rt].r,k);else return Query_rnk(tr[rt].l,k-tr[tr[rt].r].siz-1);}int cmp(Line a,Line b){return a.val<b.val;}int cmp2(query a,query b){return a.x<b.x;}int fa[N],ans[M];int find(int x){if(x==fa[x])return x;else return fa[x]=find(fa[x]);}int main(){scanf(“,&n,&m,&q);for(int i=1;i<=n;i++)scanf(“%d”,&val[i]),insert(root[i],val[i],i),fa[i]=i;for(int i=1;i<=m;i++)scanf(“,&l[i].from,&l[i].to,&l[i].val);for(int i=1;i<=q;i++)scanf(“,&que[i].v,&que[i].x,&que[i].k),que[i].no=i;sort(l+1,l+m+1,cmp);sort(que+1,que+q+1,cmp2);int tmp1=1;for(int i=1;i<=q;i++){while(tmp1<=m&&l[tmp1].val<=que[i].x){int x=find(l[tmp1].from),y=find(l[tmp1].to);tmp1++;if(x==y)continue;if(tr[root[x]].siz>tr[root[y]].siz)swap(x,y);merge(root[x],root[y]);fa[x]=y;}ans[que[i].no]=Query_rnk(root[find(que[i].v)],que[i].k);}for(int i=1;i<=q;i++)printf(“%d\n”,ans[i]); }

，你要以乐观的态度看待这个世界，你会发现世界是如此得美好