[itint5]支持删除的后继查询 - 阿牧遥 - 博客园

[itint5]支持删除的后继查询 - 阿牧遥 - 博客园
这一题一开始想到是用HashSet+链表来做，链表记录prev和next。这样也可以，后来看到都是连续的整数，而且交流了一下觉得可以用类似并查集的方式来做，一个数组，每个位置记录该位置的直接后继，删除元素时更改后继。

vector<int> vec; void init(int N) {     vec.resize(N);     for (int i = 0; i < N; i++) {         vec[i] = i;     } } void removeNum(int x) {     if (x >= vec.size()) return;     vec[x] = query(x+1); } int query(int x) {     if (x >= vec.size()) return -1;     if (vec[x] == x || vec[x] == -1) {         return vec[x];     }     int next = query(vec[x]);     vec[x] = next;     return next; }

https://github.com/Wizmann/ACM-ICPC/blob/master/itint5/cpp/%E6%94%AF%E6%8C%81%E5%88%A0%E9%99%A4%E7%9A%84%E5%90%8E%E7%BB%A7%E6%9F%A5%E8%AF%A2.cc
int n;
vector<int> father;

void init(int N) {
    n = N;
    father.resize(N + 1);
    for (int i = 0; i < N + 1; i++) {
        father[i] = i;
    }
}

int find_father(int x) {
    if (father[x] == x) {
        return x;
    }
    return father[x] = find_father(father[x]);
}


void removeNum(int x) {
    father[x] = find_father(x + 1);
}
int query(int x) {
    int res = find_father(x);
    if (res == n) {
        return -1;
    }
    return res;
}
http://fayaa.com/code/view/27800/
Read full article from [itint5]支持删除的后继查询 - 阿牧遥 - 博客园