Trie 、并查集、堆

Trie：

Trie：高效存储和查找字符串集合的数据结构

#include <iostream>
using namespace std;
const int N = 100010;
char str[N];
int son[N][26], cnt[N], idx; // 下标是 0 的点，即是根节点，又是空节点

void insert(char str[]) {
    int p = 0;// 从根节点开始
    for (int i = 0; str[i]; i ++) {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx; // 无路则插入字母
        p = son[p][u]; 
    }
    cnt[p] ++;
}

int query(char str[]) {
    int p = 0;
    for (int i = 0; str[i]; i ++) {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main() {
    int n; cin >> n;
    while(n --) {
        string op;
        cin >> op >> str;
        if(op == "I") insert(str);
        else cout << query(str) << endl;
    }
    return 0;
}

// 最大异或对
# include <iostream>
using namespace std;
const int N = 100010, M = 31 * N;
int a[N], son[M][2], idx;

void insert(int x) {
    int p = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int query(int x) {
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i --){
        int u = x >> i & 1;
        // cout << u << endl;
        if(son[p][!u]) { //如果另外一个方向存在的话就走到另外一个方向上去
            p = son[p][!u]; 
            res = res * 2 + !u;
        }
        else {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}

int main() {
    int n; cin >> n;
    int res = 0;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++){
        insert(a[i]);
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }
    cout << res << endl;
}

并查集：

并查集：快速合并两个集合，询问两个元素是否在同一个集合中。两个操作都是近乎 $O(1)$ 的时间复杂度。

基本原理：每个集合使用树来维护和表示，每个集合的表示是根节点，每个节点存储它的父节点。

问题1：判断根节点(即集合表示)： $if(p[x]==x)$

问题2：求元素 $x$ 的集合编号： $while(p[x]!=x) x=p[x]$ ，直到走到树根。

问题3：合并两个集合：px 是 x 的集合编号，py 是 y 的集合编号，p[x] = y 即可；

树高度优化：路径压缩。

#include <iostream>
using namespace std;
const int N = 100010;
int p[N], size[N];
int find(int x) { // 返回 x 所在集合(根节点),优化路径
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        p[i] = i; // 初始自成集合
    }
    while(m -- ){
        string op;
        int a, b;
        cin >> op >> a >> b;
        if(op == "M") p[find(a)] = find(b);
        else {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
}

// 带额外信息的并查集
#include <iostream>
using namespace std;
const int N = 100010;
int p[N], s[N];
int find(int x) { // 返回 x 所在集合(根节点),优化路径
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        p[i] = i; s[i] = 1; // 初始自成集合
    }
    while(m -- ){
        string op;
        int a, b;
        cin >> op;
        if(op == "C") {
            cin >> a >> b;
            if(find(a) == find(b)) continue;
            s[find(b)] += s[find(a)];
            p[find(a)] = find(b);
        }
        else if (op == "Q1"){
            cin >> a >> b;
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else {
            cin >> a;
            cout << s[find(a)] << endl;
        }
    }
}

// 食物链：维护一个并查集，关键是确定每个点和根节点的关系
#include <iostream>
using namespace std;
const int N = 50050;
int n, m;
int p[N], d[N];
int find(int x){
    if(p[x] != x) {
        // d[x] += d[p[x]];
        // p[x] = find(p[x]); // 错的
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) p[i] = i;
    int res = 0;
    while(m --){
        int t, x, y;
        cin >> t >> x >> y;
        if(x > n || y > n) res ++;
        else{
            int px = find(x), py = find(y);
            if(t == 1){ // 同类
                if(px == py && (d[y] - d[x]) % 3) res ++; // 模3为0说明是同类，不为0不是同类
                else if(px != py){
                    p[px] = py;
                    d[px] = d[y] - d[x];// x 和 y 是同类，现在根是 py，则 x 到 py 的距离和 y 到 py 的距离一样：y -> py <- px <- x
                }
            }else {
                if(px == py && (d[y] - d[x] - 1) % 3) res ++; // 模3为1说明 y 被 x 吃，否则 y 不被 x 吃
                else if (px != py){
                    p[px] = py;
                    d[px] = d[y] - d[x] - 1; // 维护距离
                }
            }
        }
    }
    cout << res << endl;
}

堆：

堆：维护一个快速求最值的数据结构，是个完全二叉树。

基本操作：插入，求最小值，删除最小值。

令：删除任意一个元素，修改任意一个元素。

以小根堆为例：节点的值 $\leq$ 节点的左右儿子值。

用一维数组存，数组下标从 $1$ 开始，设节点下标为 $x$ 则左二子为 $2x$ ，右儿子为 $2x+1$ 。

元操作：down 和 up。

down：根节点变大后将其下沉到合适的位置；up：节点变小后，检查堆将其上浮到合适位置。

设堆元素个数为 size，则：

插入操作：heap[++ size] = x, 执行 up(size) 操作。

删除操作：将堆顶用最后一个元素替换 heap[1] = heap[size]，size --，然后执行 down(1) 操作。

删除任意元素：heap[k] = heap[size], size --, down(k), up(k); (up 和 down 只会执行一个，如果变大会执行down 操作，反之会执行 up 操作。)

修改任意元素：heap[k] = x, down(k), up(k);

#include <iostream>
using namespace std;
const int N = 100010;
int h[N], cap; // cap为堆当前容量

void down(int u) {
    int t = u; // 三个点钟最小值编号，初值为当前节点，接着和左右儿子比较
    if(u * 2 <= cap && h[u * 2] < h[t]) t = u * 2; // 左二子存在且小于当前节点
    if(u * 2 + 1 <= cap && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(t != u) { // u != t 说明根节点小于左右儿子中的一个，故需要下沉, 交换后递归处理
        swap(h[t], h[u]);
        down(t);
    }
}

void up(int u) {
    while(u / 2 && h[u / 2] > h[u]){ // 有父节点且比当前大
        swap(h[u / 2], h[u]); // 则换上去
        u /= 2;
    }
}
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    cap = n;
    for (int i = n / 2; i; i --) down(i);
    while(m --) {
        cout << h[1] << " ";
        h[1] = h[cap --];
        down(1);
    }
    return 0;
}

// 带交换的堆
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int h[N], ph[N], hp[N], cap, idx; // cap为堆当前容量, ph[k] 为堆里第 k 个插入数的下标, hp[j] 为堆里下标为 j 的数是第几个插入的，ph[k] = j, hp[j] = k

void heap_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]); // 交换指针
    swap(hp[a], hp[b]); // 交换反向指针 // 上两个可以交换执行顺序
    swap(h[a], h[b]);
}

void down(int u) {
    int t = u; // 三个点钟最小值编号，初值为当前节点，接着和左右儿子比较
    if(u * 2 <= cap && h[u * 2] < h[t]) t = u * 2; // 左儿子存在且小于当前节点
    if(u * 2 + 1 <= cap && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(t != u) { // u != t 说明根节点小于左右儿子中的一个，故需要下沉, 交换后递归处理
        heap_swap(t, u);
        down(t);
    }
}

void up(int u) {
    while(u / 2 && h[u / 2] > h[u]){ // 有父节点且比当前大
        heap_swap(u / 2, u); // 则换上去
        u /= 2;
    }
}
int main() {
    int n; cin >> n;
    while(n --) {
        string op; cin >> op;
        int k, x;
        if(!strcmp(op.c_str(), "I")){
            cin >> x; cap ++;
            ph[++ idx] = cap, hp[cap] = idx;
            h[cap] = x;
            up(cap);
        }else if(!strcmp(op.c_str(), "PM")) cout << h[1] << endl;
        else if(!strcmp(op.c_str(), "DM")) {
            heap_swap(1, cap);
            cap --;
            down(1);
        }else if(op == "D") {
            cin >> k;
            k = ph[k];
            heap_swap(k, cap);
            cap --;
            down(k), up(k);
        }else{
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k), up(k);
        }
    }
    return 0;
}

Q.E.D.