題目大意:
每個點有一個權值.并查集.在集合合并的程序中查詢集合第k大.
題目思路:
并查集,每個點開個線段樹.然后在并查集集合合并的程序中同時線段樹合并即可.
AC代碼:
#include<bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
const int maxn = 1e5 + 5;
int sum[maxn << 5] , ls[maxn << 5] , rs[maxn << 5] , rt[maxn] , tot;
void pushup (int t)
{
int tl = ls[t] , tr = rs[t];
sum[t] = sum[tl] + sum[tr];
}
int add (int l , int r , int t , int p , int c)
{
int now = ++tot;
ls[now] = ls[t];
rs[now] = rs[t];
if (l == r) {
sum[now] += c;
return now;
}
if (p <= mid) ls[now] = add(l , mid , ls[now] , p , c);
else rs[now] = add(mid + 1 , r , rs[now] , p , c);
pushup(now);
return now;
}
int ask (int l , int r , int t , int k){
if (l == r) return l;
if (sum[ls[t]] >= k) return ask(l , mid , ls[t] , k);
return ask(mid + 1 , r , rs[t] , k - sum[ls[t]]);
}
int mer (int a , int b , int l , int r)
{
if (!a) return b;
if (!b) return a;
if (l == r) {
sum[a] += sum[b];
return a;
}
ls[a] = mer (ls[a] , ls[b] , l , mid);
rs[a] = mer (rs[a] , rs[b] , mid + 1 , r);
pushup(a);
return a;
}
int a[maxn] , f[maxn] , n , m , id[maxn];
int getf (int x){return f[x]==x?x:f[x]=getf(f[x]);}
int dsu_mer (int a , int b){
int fa = getf(a) , fb = getf(b);
if (fa == fb) return false;
f[fb] = fa;
mer(rt[fa] , rt[fb] , 1 , n);
return true;
}
int main()
{
scanf("%d%d" , &n , &m);
for (int i = 1; i <= n ; i++){
scanf("%d" , a + i);
id[a[i]] = i;
f[i] = i;
rt[i] = add(1 , n , rt[0] , a[i] , 1);
}
for (int i = 1; i <= m ; i++){
int x , y; scanf("%d%d" , &x , &y);
dsu_mer (x , y);
}
char op[5];
int x , y , q;scanf("%d" , &q);
for (int i = 1; i <= q ; i++){
scanf("%s" , op);
scanf("%d%d" , &x , &y);
if (op[0] == 'Q'){
x = getf (x);
if (sum[rt[x]] < y){
printf("-1\n");
}else {
printf("%d\n" , id[ask(1 , n , rt[x] , y)]);
}
}else {
dsu_mer (x , y);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/172470.html
標籤：其他
上一篇：linux虛擬機vmware,VM虛擬機——vmware 14
下一篇：鐵威馬NAS忘記密碼找回方式