永無鄉

?HYSBZ - 2733?

永無鄉包含 n 座島，編號從 1 到 n，每座島都有自己的獨一無二的重要度，按照重要度可 以將這 n 座島排名，名次用 1 到 n 來表示。某些島之間由巨大的橋連接，通過橋可以從一個島 到達另一個島。如果從島 a 出發經過若干座（含 0 座）橋可以到達島 b，則稱島 a 和島 b 是連 通的。現在有兩種操作：B x y 表示在島 x 與島 y 之間修建一座新橋。Q x k 表示詢問當前與島 x連通的所有島中第 k 重要的是哪座島，即所有與島 x 連通的島中重要度排名第 k 小的島是哪 座，請你輸出那個島的編號。?
?

Input

輸入文件第一行是用空格隔開的兩個正整數 n 和 m，分別 表示島的個數以及一開始存在的橋數。接下來的一行是用空格隔開的 n 個數，依次描述從島 1 到島 n 的重要度排名。隨后的 m 行每行是用空格隔開的兩個正整數 ai 和 bi，表示一開始就存 在一座連接島 ai 和島 bi 的橋。后面剩下的部分描述操作，該部分的第一行是一個正整數 q， 表示一共有 q 個操作，接下來的 q 行依次描述每個操作，操作的格式如上所述，以大寫字母 Q 或B 開始，后面跟兩個不超過 n 的正整數，字母與數字以及兩個數字之間用空格隔開。 對于 20%的數據 n≤1000,q≤1000
?
對于 100%的數據 n≤100000,m≤n，q≤300000?
?

Output

對于每個 Q x k 操作都要依次輸出一行，其中包含一個整數，表 示所詢問島嶼的編號。如果該島嶼不存在，則輸出-1。?
?

Sample Input5 1 4 3 2 5 1 1 2 7 Q 3 2 Q 2 1 B 2 3 B 1 5 Q 2 1 Q 2 4 Q 2 3

Sample Output-1 2 5 1 2

?

sol：線段樹合并板子題，像權值線段樹一樣搞一搞，記錄當前這個值域中有幾個數組，來查詢第k大

#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() {ll s=0;bool f=0;char ch=' ';while(!isdigit(ch)){f|=(ch=='-'); ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) {if(x<0){putchar('-'); x=-x;}if(x<10){putchar(x+'0'); return;}write(x/10);putchar((x%10)+'0');return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar('\n') const int N=100005; int n,m,Q,island[N],rnk[N],fa[N],sz[N]; inline int gf(int x){return (fa[x]==x)?(x):(fa[x]=gf(fa[x]));} int rt[N],cnt=0; struct Node {int ls,rs,sum; }T[N*50]; inline void Insert(int &x,int l,int r,int Pos) {if(!x) x=++cnt;T[x].sum++;if(l==r) return;int mid=(l+r)>>1;if(Pos<=mid) Insert(T[x].ls,l,mid,Pos);else Insert(T[x].rs,mid+1,r,Pos);T[x].sum=T[T[x].ls].sum+T[T[x].rs].sum; } inline int Merg(int x,int y,int l,int r) {if(!x) return y;if(!y) return x;int mid=(l+r)>>1;T[x].ls=Merg(T[x].ls,T[y].ls,l,mid);T[x].rs=Merg(T[x].rs,T[y].rs,mid+1,r);T[x].sum=T[T[x].ls].sum+T[T[x].rs].sum;return x; } inline void combine(int x,int y) {int fx=gf(x),fy=gf(y);sz[fx]+=sz[fy]; fa[fy]=fx;rt[fx]=Merg(rt[fx],rt[fy],1,n); } inline int Ask(int x,int l,int r,int Id) {if(l==r) return l;int mid=(l+r)>>1;if(T[T[x].ls].sum>=Id) return Ask(T[x].ls,l,mid,Id);else return Ask(T[x].rs,mid+1,r,Id-T[T[x].ls].sum); } int main() {int i,x,y; char opt[5];R(n); R(m);for(i=1;i<=n;i++){sz[i]=1; fa[i]=i; island[rnk[i]=read()]=i;Insert(rt[i],1,n,rnk[i]);} // cout<<"@@@@@@@@@@@@@@@@@@@@"<<endl;for(i=1;i<=m;i++) combine(read(),read());R(Q);while(Q--){scanf("%s",opt+1); R(x); R(y);if(opt[1]=='B') combine(x,y);else{int fx=gf(x);if(sz[fx]<y) puts("-1"); else Wl(island[Ask(rt[fx],1,n,y)]);}}return 0; } /* Sample Input 5 1 4 3 2 5 1 1 2 7 Q 3 2 Q 2 1 B 2 3 B 1 5 Q 2 1 Q 2 4 Q 2 3 Sample Output -1 2 5 1 2 */ View Code

?

轉載于:https://www.cnblogs.com/gaojunonly1/p/11173504.html

總結

以上是生活随笔為你收集整理的bzoj2733永无乡的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。