正題

題目鏈接:https://www.luogu.com.cn/problem/P3224

---

題目大意

$n$個(gè)點(diǎn)，每次可以連接兩個(gè)點(diǎn)和詢問一個(gè)點(diǎn)所在聯(lián)通塊中第$k$大的數(shù)。

---

解題思路

我們發(fā)現(xiàn)可以啟發(fā)式合并，對于每個(gè)聯(lián)通塊維護(hù)一個(gè)線段樹，然后每次合并時(shí)將小的暴力丟入大的平很樹里，然后詢問即可。

時(shí)間復(fù)雜度$O(n{\log }^{2}n)$

（其實(shí)可以用權(quán)線合并做到$O(n\log n)$，但是在練平衡樹就算了）

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10,M=6e6+10; struct node{int to,next; }a[N]; int n,m,tot,p[N],siz[N],rt[N],ls[N]; struct Treap{int tot,rt[N],siz[M],cnt[M],ls[M],rs[M],val[M],dat[M];void Updata(int x){siz[x]=siz[ls[x]]+siz[rs[x]]+cnt[x];return;}void zig(int &x){int y=ls[x];ls[x]=rs[y];rs[y]=x;x=y;Updata(rs[x]);Updata(x);return;}void zag(int &x){int y=rs[x];rs[x]=ls[y];ls[y]=x;x=y;Updata(ls[x]);Updata(x);return;}void Insert(int &x,int w){if(!x){x=++tot;val[x]=w;cnt[x]=siz[x]=1;dat[x]=rand()*rand();return;}if(p[w]==p[val[x]])cnt[x]++,Updata(x);if(p[w]<p[val[x]]){Insert(ls[x],w);if(dat[x]<dat[ls[x]])zig(x);}else{Insert(rs[x],w);if(dat[x]>dat[rs[x]])zag(x);}Updata(x);return;}int GetVal(int x,int rank){if(!x)return 0;if(rank>siz[x])return -1;if(siz[ls[x]]>=rank)return GetVal(ls[x],rank);if(siz[ls[x]]+cnt[x]>=rank)return val[x];return GetVal(rs[x],rank-siz[ls[x]]-cnt[x]); } }T; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa){T.Insert(T.rt[rt[x]],x);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;rt[y]=rt[x];dfs(y,x);} } void Merge(int x,int y){x=rt[x];y=rt[y];if(x==y)return;if(siz[x]<siz[y])swap(x,y);rt[y]=rt[x];siz[x]+=siz[y];addl(x,y);dfs(y,x);return; } int main() {scanf("%d%d",&n,&m);srand(n*m);for(int i=1;i<=n;i++){scanf("%d",&p[i]);rt[i]=i;T.Insert(T.rt[i],i);siz[rt[i]]=1;}while(m--){int x,y;scanf("%d%d",&x,&y);Merge(x,y);}scanf("%d",&m);while(m--){char op[4];int x,y;scanf("%s %d %d",op,&x,&y);if(op[0]=='Q')printf("%d\n",T.GetVal(T.rt[rt[x]],y));else Merge(x,y);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3224-[HNOI2012]永无乡【平衡树,启发式合并】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。