傳送門

【題目分析】

線段樹合并裸題了吧。。。。

將每個島視作一棵權(quán)值線段樹，然后直接按照題目意思去進行合并，由于只有查詢第K大島的詢問，所以merge過程就直接遞歸到葉子節(jié)點，一直合并size即可。

第一次寫線段樹合并結(jié)果有一個地方寫錯調(diào)了半天，唉。。。

【代碼~】

#include<bits/stdc++.h> using namespace std; const int MAXN=1e5+10;int n,m,q; int a[MAXN]; int tot,fa[MAXN],id[MAXN]; int lc[MAXN*20],rc[MAXN*20],siz[MAXN*20],rt[MAXN*20];int Read(){int i=0,f=1;char c;for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());if(c=='-')f=-1,c=getchar();for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';return i*f; }int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]); }void update(int &root,int l,int r,int k){if(!root)root=++tot;siz[root]++;if(l==r)return ;int mid=l+r>>1;if(k<=mid)update(lc[root],l,mid,k);elseupdate(rc[root],mid+1,r,k); }void merge(int &x,int y){if(!x||!y){x+=y;return ;}siz[x]+=siz[y];merge(lc[x],lc[y]);merge(rc[x],rc[y]); }void build(){for(int i=1;i<=n;++i){fa[i]=i;a[i]=Read();id[a[i]]=i;update(rt[i],1,n,a[i]);}for(int i=1;i<=m;++i){int x=Read(),y=Read();int fx=find(x),fy=find(y);if(fx!=fy){if(siz[rt[fx]]>siz[rt[fy]])fa[fx]=fy,merge(rt[fy],rt[fx]);elsefa[fy]=fx,merge(rt[fx],rt[fy]);}} }int query(int root,int l,int r,int k){if(l==r)return l;int x=siz[lc[root]];int mid=l+r>>1;if(k<=x)return query(lc[root],l,mid,k);elsereturn query(rc[root],mid+1,r,k-x); }int main(){n=Read(),m=Read();build();q=Read();while(q--){char cz[10];scanf("%s",cz);int x=Read(),y=Read();if(cz[0]=='B'){int fx=find(x),fy=find(y);if(fx!=fy){if(siz[rt[fx]]>siz[rt[fy]])fa[fx]=fy,merge(rt[fy],rt[fx]);elsefa[fy]=fx,merge(rt[fx],rt[fy]);}}else{x=find(x);if(siz[rt[x]]<y)puts("-1");elsecout<<id[query(rt[x],1,n,y)]<<'\n';}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Ishtar/p/10291853.html

總結(jié)

以上是生活随笔為你收集整理的洛谷3224 【HAOI2012】永无乡（线段树合并）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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