$$\LARGE{\color{purple}{\mathbf{Note-算法进阶课} } }$$
永无乡
1.首先可以知道题目要求我们能够维护岛与岛之间的连通性(只有加边而没有删边操作)$\rightarrow $ 并查集
2.其次需要维护动态查询第 $k$ 个数 $\rightarrow $ 平衡树(vector模拟也不是不行(doge),甚至AC)
3.动态支持合并操作 $\rightarrow$ 启发式合并
启发式合并:每次优先将小的集合合并到大的集合,时间复杂度可以达到 $O(n\log n)$
ps:
1. 这里 splay 维护的关键字 $v$ 是岛屿的重要度,同时需要开空间记录序号 $id$ ,表示它是哪个岛
2. 对于每个初始的岛,我们对每个岛建立一株 splay树,我们用 root[N] 存储每株 splay 的根
3. 加边操作就是 将节点数少的 splay 树的节点查到节点数大的 splay 中,同时调整并查集
关于 splay 的基本操作,参考
法1.splay
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 1800010;
constexpr int M = 100010;
struct Node
{
int s[2],v,p,id;
int sz;
void init(int _v,int _id,int _p)
{
v = _v,p = _p,sz = 1,id = _id;
}
}tr[N];
int root[M],idx,p[M];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void pushup(int u)
{
tr[u].sz = tr[tr[u].s[0]].sz + tr[tr[u].s[1]].sz + 1;
}
void rotate(int x)
{
int y = tr[x].p,z = tr[y].p;
int k = (x == tr[y].s[1]);
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y),pushup(x);
}
void splay(int x,int k,int d)
{
while(tr[x].p != k)
{
int y = tr[x].p,z = tr[y].p;
if(z != k)
if((x == tr[y].s[1]) ^ (y == tr[z].s[1])) rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root[d] = x;
}
void insert(int x,int id,int d)
{
int u = root[d],p = 0;
while(u) p = u,u = tr[u].s[x > tr[u].v];
u = ++ idx;
if(p) tr[p].s[x > tr[p].v] = u;
tr[u].init(x,id,p);
splay(u,0,d);
}
int kth(int k,int d)
{
int u = root[d];
while(u)
{
if(tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
else if(tr[tr[u].s[0]].sz + 1 == k) return tr[u].id;
else k -= tr[tr[u].s[0]].sz + 1,u = tr[u].s[1];
}
return -1;
}
void dfs(int u,int d)
{
if(tr[u].s[0]) dfs(tr[u].s[0],d);
if(tr[u].s[1]) dfs(tr[u].s[1],d);
insert(tr[u].v,tr[u].id,d);
}
void merge(int a,int b)
{
a = find(a),b = find(b);
if(a != b)
{
if(tr[root[a]].sz > tr[root[b]].sz) swap(a,b);
dfs(root[a],b);
p[a] = b;
}
}
int main()
{
fastio();
int n,m;cin >> n >> m;
for(int i = 1,v;i <= n;i ++ )
{
p[i] = root[i] = i,
cin >> v;
tr[++ idx].init(v,i,0);
}
while(m -- )
{
int l,r;
cin >> l >> r;
merge(l,r);
}
int q;cin >> q;
while(q -- )
{
int a,b;
char op[2];
cin >> op >> a >> b;
if(*op == 'Q')
{
a = find(a);
if(b <= tr[root[a]].sz) cout << kth(b,a) << endl;
else cout << -1 << endl;
}
else merge(a,b);
}
return 0;
}
法2.vector模拟平衡树
#include <bits/stdc++.h>
#define fastio() ios::sync_with_stdio(0),\
cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TRI;
typedef unsigned long long ULL;
constexpr int N = 100010;
int p[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct BST
{
vector<int> S;
vector<int> id;
inline void insert(int x,int _d)
{
auto d = S.begin();
auto it = lower_bound(S.begin(),S.end(),x);
S.emplace(it,x);
id.emplace(it - d + id.begin(),_d);
}
inline void erase(int x)
{
auto d = S.begin();
auto it = lower_bound(S.begin(),S.end(),x);
S.erase(it);
id.erase(it - d + id.begin());
}
inline int rk(int x)
{
return lower_bound(S.begin(),S.end(),x) - S.begin() + 1;
}
inline int kth(int k)
{
return id[k - 1];
}
}tr[N];
void merge(int a,int b)
{
a = find(a),b = find(b);
if(a != b)
{
if(tr[a].S.size() > tr[b].S.size()) swap(a,b);
for(int i = 0;i < tr[a].S.size();i ++ )
tr[b].insert(tr[a].S[i],tr[a].id[i]);
p[a] = b;
}
}
int main()
{
fastio();
int n,m;cin >> n >> m;
for(int i = 1,v;i <= n;i ++ )
{
cin >> v;p[i] = i;
tr[i].insert(v,i);
}
while(m -- )
{
int l,r;
cin >> l >> r;
merge(l,r);
}
int q;cin >> q;
while(q -- )
{
int a,b;
char op[2];
cin >> op >> a >> b;
if(*op == 'Q')
{
a = find(a);
if(b <= tr[a].S.size()) cout << tr[a].kth(b) << endl;
else cout << -1 << endl;
}
else merge(a,b);
}
return 0;
}