[题解] [HNOI2012] 永无乡

题面

题解

题面很清楚

问题是要怎么做

其实就是查询一个动态集合的第 \(k\) 大

每次合并就把两个集合黏在一起就行了

我们可以想到用 splay 来写, 启发式合并一下就行

还有一种思路是权值线段树合并

每一次连边就相当于是一次合并

好像确实没有什么很难想的地方, 思路很顺啊

就是线段树合并的复杂度实在是不会分析

这里给出两种方式的代码

Code

splay

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 100005; 
using namespace std;

int n, m, q, pa[N], rt[N]; 
struct Tree { int ch[2], fa, sz, val; } t[N]; 
char s[15]; 

template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}

int getf(int x) { return pa[x] ^ x ? pa[x] = getf(pa[x]) : x; }

void pushup(int p) { t[p].sz = t[t[p].ch[0]].sz + t[t[p].ch[1]].sz + 1; }

void rotate(int x)
{
    int y = t[x].fa, z = t[y].fa, k = t[y].ch[1] == x;
    t[z].ch[t[z].ch[1] == y] = x, t[x].fa = z;
    t[y].ch[k] = t[x].ch[k ^ 1], t[t[x].ch[k ^ 1]].fa = y;
    t[x].ch[k ^ 1] = y, t[y].fa = x;
    pushup(y), pushup(x); 
}

void splay(int x, int goal)
{
    while(t[x].fa != goal)
    {
        int y = t[x].fa, z = t[y].fa;
        if(z != goal)
            (t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? rotate(x) : rotate(y);
        rotate(x); 
    }
}

void insert(int x, int u)
{
    splay(u, 0); int ff = 0; 
    while(u)
        ff = u, u = t[u].ch[t[x].val > t[u].val];
    t[x].ch[0] = t[x].ch[1] = 0, t[x].sz = 1, t[x].fa = ff;
    if(ff) t[ff].ch[t[x].val > t[ff].val] = x;
    splay(x, 0); 
}

void modify(int u, int fa)
{
    if(!u) return;
    modify(t[u].ch[0], fa); 
    modify(t[u].ch[1], fa); 
    insert(u, fa); 
}

void merge(int u, int v)
{
    u = getf(u), v = getf(v); 
    splay(u, 0), splay(v, 0); 
    if(t[u].sz < t[v].sz) swap(u, v); 
    modify(v, u); 
}

void output(int u)
{
    if(!u) return;
    output(t[u].ch[0]);
    printf("%d ", u);
    output(t[u].ch[1]); 
}

int kth(int x, int y)
{
    int u = getf(x); splay(u, 0); 
    if(t[u].sz < y) return -1; 
    while(u)
    {
        if(y <= t[t[u].ch[0]].sz)
            u = t[u].ch[0];
        else if(y > t[t[u].ch[0]].sz + 1)
            y -= t[t[u].ch[0]].sz + 1, u = t[u].ch[1];
        else return u; 
    }
}

int main()
{
    n = read <int> (), m = read <int> ();
    for(int i = 1; i <= n; i++)
        t[i].val = read <int> (), t[i].sz = 1, pa[i] = i; 
    for(int u, v, i = 1; i <= m; i++)
    {
        u = getf(u = read <int> ()), v = getf(v = read <int> ());
        if(u == v) continue; 
        merge(u, v), pa[getf(v)] = getf(u); 
    }
    q = read <int> (); 
    int x, y; 
    while(q--)
    {
        scanf("%s", s + 1), x = read <int> (), y = read <int> ();
        if(s[1] == 'B')
        {
            x = getf(x), y = getf(y);
            if(x == y) continue;
            merge(x, y), pa[getf(y)] = getf(x); 
        }
        if(s[1] == 'Q')
            printf("%d\n", kth(x, y)); 
    }
    return 0; 
}
/*
  7 3
1 3 6 2 5 7 4
1 4
4 7
4 6
4
B 2 3
B 2 5
B 5 4
Q 4 2
 */

我没写 else 调了一个多小时(滑稽

线段树合并

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 100005; 
using namespace std;

int n, m, q, pa[N], rt[N], cnt; 
struct Tree { int l, r, sz, id; } t[N * 32]; 
char s[15]; 

template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}

int getf(int x) { return pa[x] ^ x ? pa[x] = getf(pa[x]) : x; }

void modify(int &p, int l, int r, int k, int x)
{
    p = ++cnt; t[p].sz++;
    if(l == r)
        return (void) (t[p].id = x); 
    int mid = (l + r) >> 1; 
    if(k <= mid) modify(t[p].l, l, mid, k, x);
    else modify(t[p].r, mid + 1, r, k, x); 
}

int merge(int p, int o, int l, int r)
{
    if(!p || !o) return p + o; 
    t[p].sz += t[o].sz;
    if(l == r)
        return t[p].id = t[p].id + t[o].id, p; 
    int mid = (l + r) >> 1;
    t[p].l = merge(t[p].l, t[o].l, l, mid);
    t[p].r = merge(t[p].r, t[o].r, mid + 1, r);
    return p; 
}

int query(int p, int l, int r, int k)
{
    if(l == r)
        return t[p].id;
    int mid = (l + r) >> 1, sum = t[t[p].l].sz;
    if(k <= sum) return query(t[p].l, l, mid, k);
    else return query(t[p].r, mid + 1, r, k - sum); 
}

int main()
{
    n = read <int> (), m = read <int> ();
    for(int x, i = 1; i <= n; i++)
        pa[i] = i, x = read <int> (), modify(rt[i], 1, n, x, i);
    for(int u, v, i = 1; i <= m; i++)
    {
        u = getf(u = read <int> ()), v = getf(v = read <int> ());
        if(u == v) continue;
        rt[u] = merge(rt[u], rt[v], 1, n), pa[getf(v)] = getf(u); 
    }
    q = read <int> (); 
    int x, y; 
    while(q--)
    {
        scanf("%s", s + 1), x = read <int> (), y = read <int> (); 
        if(s[1] == 'B')
        {
            x = getf(x), y = getf(y);
            if(x == y) continue;
            merge(rt[x], rt[y], 1, n), pa[getf(y)] = getf(x); 
        }
        if(s[1] == 'Q')
        {
            printf("%d\n", t[rt[getf(x)]].sz < y ? -1 : query(rt[getf(x)], 1, n, y));
        }
    }
    return 0; 
}

超级好写, 一下就写完了

[题解] [HNOI2012] 永无乡

原文：https://www.cnblogs.com/ztlztl/p/12189674.html