洛谷 P3224 [HNOI2012]永无乡

zrzring 2020-06-04 PM 35℃ 0条

这个题一看第k大就非常平衡树,于是我们很容易想到启发式合并平衡树的做法

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf 1e9
#define ls son[x][0]
#define rs son[x][1]
using namespace std;
void file() {
    freopen("read.in", "r", stdin);
    freopen("write.out", "w", stdout);
}
const int N = 1e6 + 10;
inline int read() {
    int sym = 0, res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
int n, m, w[N], s[N], top;
int son[N][2], num[N], siz[N], val[N], set[N], fa[N], rt[N];
void pushup(int x) {
    siz[x] = siz[ls] + siz[rs] + 1;
}
int l_r(int x) {
    return x == son[fa[x]][1];
}
void rotate(int x, int &goal) {
    int y = fa[x], z = fa[y], kind = l_r(x);
    if (y == goal) goal = x; else son[z][l_r(y)] = x;
    son[y][kind] = son[x][kind ^ 1]; fa[son[x][kind ^ 1]] = y;
    son[x][kind ^ 1] = y; fa[y] = x; fa[x] = z;
    pushup(y); pushup(x);
}
void splay(int x, int &goal) {
    for (int y = fa[x]; x != goal; y = fa[x]) {
        if (y != goal) rotate(l_r(x) == l_r(y) ? y : x, goal);
        rotate(x, goal);
    }
}
void ins(int &x, int t, int fat = 0) {
    if (!x) {
        x = t; fa[x] = fat; siz[x] = 1; return;
    }
    ins(son[x][w[t] > w[x]], t, x); pushup(x);
}
void dfs(int x) {
    if (!x) return;
    dfs(ls); s[++top] = x; dfs(rs);
}
void merge(int x, int y) {
    if (x == y) return;
    if (siz[rt[x]] < siz[rt[y]]) swap(x, y);
    top = 0; dfs(rt[y]);
    for (int i = 1; i <= top; i++) {
        set[s[i]] = x; ins(rt[x], s[i]); splay(s[i], rt[x]);
    }
}
int query(int x, int k) {
    while (1) {
        if (siz[ls] >= k) x = ls;
        else {
            k -= siz[ls] + 1; if (k <= 0) {splay(x, rt[set[x]]); return x;} x = rs;
        }
    }
}
int main() { //file();
    n = read(); m = read();
    for (int i = 1; i <= n; i++) {
        w[i] = read(); rt[i] = set[i] = i; siz[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        int x = set[read()], y = set[read()]; if (x != y) merge(x, y);
    }
    int q = read();
    for (int i = 1; i <= q; i++) {
        char opt[10]; scanf("%s", opt);
        if (opt[0] == 'Q') {
            int x = set[read()], k = read(); 
            if (siz[rt[x]] < k) printf("-1\n"); printf("%d\n", query(rt[set[x]], k));
        } else {
            int x = set[read()], y = set[read()]; if (x != y) merge(x, y);
        }
    }
    return 0;
}

然后考虑如果我们只是需要第k大的话,我们用一个线段树也可以做到,只需要维护一个区间和就可以了,查找的时候类似于平衡树找第k大

对于合并这个操作,一个线段树合并就可以解决,实际上每次只有合并,并没有修改的操作,代码也非常简单

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#define inf 1e9
using namespace std;
void file() {
    freopen("read.in", "r", stdin);
    freopen("write.out", "w", stdout);
}
const int N = 5e6 + 10;
inline int read() {
    int sym = 0, res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
int num[N], tot;
int n, m, a[N], tsum[N], fa[N], rt[N], ls[N], rs[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int modify(int x, int l, int r, int goal) {
    if (!x) x = ++tot, tsum[x]++;
    if (l == r) return x; int mid = l + r >> 1;
    if (mid >= goal) ls[x] = modify(ls[x], l, mid, goal);
    else rs[x] = modify(rs[x], mid + 1, r, goal);
    return x;
}
int merge(int x, int y) {
    if (!x || !y) return x | y;
    tsum[x] += tsum[y];
    ls[x] = merge(ls[x], ls[y]);
    rs[x] = merge(rs[x], rs[y]);
    return x;
}
int query(int x, int l, int r, int k) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (tsum[ls[x]] >= k) return query(ls[x], l, mid, k);
    else return query(rs[x], mid + 1, r, k - tsum[ls[x]]);
}
int main() { //file();
    n = read(); m = read();
    for (int i = 1; i <= n; i++) {
        int x = read(); num[x] = i; fa[i] = i; rt[i] = modify(rt[i], 1, n, x);
    }
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read(), fx = find(x), fy = find(y);
        if (fx != fy) fa[fy] = fx, rt[fx] = merge(rt[fx], rt[fy]);
    }
    int q = read();
    for (int i = 1; i <= q; i++) {
        char opt[10]; scanf("%s", opt);
        if (opt[0] == 'Q') {
            int x = read(), k = read(); x = find(x);
            if (tsum[rt[x]] < k) printf("-1\n"); else printf("%d\n", num[query(rt[x], 1, n, k)]);
        } else {
            int x = read(), y = read(), fx = find(x), fy = find(y);
            if (fx != fy) fa[fy] = fx, rt[fx] = merge(rt[fx], rt[fy]);
        }
    }
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00