Link

BZOJ2733

Description

给定 $n$ 个点的图,每个点带权。

  • 每次在两个点之间建边
  • 查询 $x$ 所在联通块中,点权第 $k$ 小的编号。

数据范围:$n\leq 10^5,m\leq 3\times 10^5$

Solution

用并查集维护,将联通块内所有节点的信息记录到深度最小的节点。

每次建边相当于合并两个联通块,考虑用线段树合并来实现。

时间复杂度:$O(nlogn)$

Code

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5; 

struct edge {
    int to, nt; 
} e[N << 1];

int n, m, q, edge_cnt;
pair<int, int> disc[N];
int a[N], id[N], head[N], fa[N], root[N];

struct segment_tree {
    struct Node {
        int sum, ch[2]; 
    } tr[N * 4 * 17];
    
    int node_cnt; 
    
    Node& operator[](int x) {
        return tr[x]; 
    }
    
    void modify(int& x, int l, int r, int pos) {
        if (!x) x = ++node_cnt; 
        if (l == r) {
            tr[x].sum++; 
            return;
        }
        int mid = (l + r) >> 1;
        pos <= mid ? modify(tr[x].ch[0], l, mid, pos) : modify(tr[x].ch[1], mid + 1, r, pos);
        tr[x].sum = tr[tr[x].ch[0]].sum + tr[tr[x].ch[1]].sum; 
    }
    
    int merge(int x, int y, int l, int r) {
        if (!x || !y) return x | y;
        tr[x].sum += tr[y].sum;
        if (l == r) return x;  
        int mid = (l + r) >> 1;
        tr[x].ch[0] = merge(tr[x].ch[0], tr[y].ch[0], l, mid);
        tr[x].ch[1] = merge(tr[x].ch[1], tr[y].ch[1], mid + 1, r);
        return x; 
    }
    
    void merge(int& a, int b) {
        a = merge(a, b, 1, n); 
    }
    
    int query(int x, int l, int r, int k) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (k <= tr[tr[x].ch[0]].sum) return query(tr[x].ch[0], l, mid, k);
        else return query(tr[x].ch[1], mid + 1, r, k - tr[tr[x].ch[0]].sum);
    }
} st;

int get_fa(int x) {
    return fa[x] == x ? fa[x] : fa[x] = get_fa(fa[x]);
}

void add_edge(int u, int v) {
    e[++edge_cnt] = (edge){v, head[u]}; 
    head[u] = edge_cnt;
}

void dfs(int u, int fa, int top) {
    ::fa[u] = top; 
    st.modify(root[top], 1, n, a[u]);
    for (int it = head[u]; it; it = e[it].nt) {
        int v = e[it].to;
        if (v == fa) continue; 
        dfs(v, u, top);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &a[i]), disc[i] = make_pair(a[i], i);
    sort(disc + 1, disc + 1 + n);
    for (int i = 1; i <= n; i++)
        a[disc[i].second] = i, id[a[i]] = i; 
    for (int i = 1; i <= m; i++) {
        int u, v; 
        scanf("%d %d", &u, &v);
        add_edge(u, v); 
        add_edge(v, u); 
    }
    for (int i = 1; i <= n; i++)
        if (!fa[i]) dfs(i, 0, i);
    scanf("%d", &q);
    for (int cs = 1; cs <= q; cs++) {
        char opt[5]; 
        int x, y; 
        scanf("%s %d %d", opt, &x, &y);
        if (opt[0] == 'B') {
            int a = get_fa(x), b = get_fa(y);
            if (a != b) {
                fa[a] = b; 
                st.merge(root[b], root[a]);
            }
        } else {
            int a = get_fa(x); 
            if (st[root[a]].sum < y)
                printf("-1\n");
            else 
                printf("%d\n", id[st.query(root[a], 1, n, y)]);
        }
    }
    return 0; 
}
最后修改:2020 年 05 月 02 日 08 : 54 AM
如果觉得我的文章对你有用,请随意赞赏