数据结构

链表

0. 实现方式

在算法竞赛中，链表通常不以结构体的形式实现，原因在于建新节点的时间太长。链表通常以数组的形式实现。

1. 单链表

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 k 个插入的数后面的一个数；
3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

1. H x，表示向链表头插入一个数 x。
2. D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
3. I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000 所有操作保证合法。

输入样例：

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例：

6 4 6 5

#include <iostream>
using namespace std;
const int N = 100010;

/* 
  head 表示头节点下标
  e 表示节点i的值
  ne 表示next指针
*/
int head, e[N], ne[N], idx;

void init() {
  head = -1;
  idx = 0;
}

void add_to_head(int x) {
  e[idx] = x;
  ne[idx] = head;
  head = idx;
  idx++;
}

/* 将x插入k这个位置 */
void add(int k, int x) {
  e[idx] = x;
  ne[idx] = ne[k];
  ne[k] = idx;
  idx++;
}

/* 删除k这个节点 */
void remove(int k) {
  ne[k] = ne[ne[k]];
}

int main() {
  int m;
  
  init();
  
  cin >> m;
  while (m--) {
    int k, x;
    char op;
    
    cin >> op;
    if (op == 'H') {
      cin >> x;
      add_to_head(x);
    } else if (op == 'D') {
      cin >> k;
      if (!k) head = ne[head];
      remove(k - 1);
    } else {
      cin >> k >> x;
      add(k - 1, x);
    }
  }
  
  for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
  cout << endl;
  
  return 0;
}

2. 双链表

实现一个双链表，双链表初始为空，支持 5 种操作：

1. 在最左侧插入一个数；
2. 在最右侧插入一个数；
3. 将第 k 个插入的数删除；
4. 在第 k 个插入的数左侧插入一个数；
5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

1. L x，表示在链表的最左端插入数 x。
2. R x，表示在链表的最右端插入数 x。
3. D k，表示将第 k 个插入的数删除。
4. IL k x，表示在第 k 个插入的数左侧插入一个数。
5. IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围

1≤M≤100000 所有操作保证合法。

输入样例：

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例：

8 7 7 3 2 9

#include <iostream>
using namespace std;
const int N = 100010;

int m;
int e[N], l[N], r[N], idx;

/* two dummy nodes */
void init() {
  r[0] = 1, l[1] = 0;
  idx = 2;
}

/* 在下标为k的点的右边插入x */
void add(int k, int x) {
  e[idx] = x;
  r[idx] = r[k];
  l[idx] = k;
  l[r[k]] = idx;
  r[k] = idx;
  idx++;
}

void remove(int k) {
  r[l[k]] = r[k];
  l[r[k]] = l[k];
}

int main() {
  cin >> m;
  init();
  
  while (m--) {
    string op;
    cin >> op;
    int x, k;
    if (op == "R") {
      cin >> x;
      add(l[1], x);
    } else if (op == "L") {
      cin >> x;
      add(0, x);
    } else if (op == "D") {
      cin >> k;
      remove(k + 1);
    } else if(op == "IL") {
      cin >> k >> x;
      add(l[k + 1], x);
    } else {
      cin >> k >> x;
      add(k + 1, x);
    }
  }
  for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
  cout << endl;
  return 0;
}

栈

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围

1≤N≤105 1≤数列中元素≤109

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

#include <iostream>
using namespace std;
const int N = 100010;

int n;
int stk[N], tt;

int main() {
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    while (tt && stk[tt] >= x) tt--;
    if (tt) printf("%d ", stk[tt]);
    else printf("-1 ");
    
    stk[++tt] = x;
  }
  return 0;
}

队列

给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

#include <iostream>
using namespace std;
const int N = 1000010;

int n, k;
int a[N], q[N];

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  
  int hh = 0, tt = -1;
  for (int i = 0; i < n; i++) {
    /* 判断队头是否已滑出窗口 */
    if (hh <= tt && i - k + 1 > q[hh]) hh++;
    while (hh <= tt && a[q[tt]] >= a[i]) tt--;
    q[++tt] = i;
    if (i >= k - 1) printf("%d ", a[q[hh]]);
  }
  puts("");
  
  hh = 0, tt = -1;
  for (int i = 0; i < n; i++) {
    if (hh <= tt && i - k + 1 > q[hh]) hh++;
    while (hh <= tt && a[q[tt]] <= a[i]) tt--;
    q[++tt] = i;
    if (i >= k - 1) printf("%d ", a[q[hh]]);
  }
  puts("");
  
  return 0;
}

kmp算法

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M，表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

1≤N≤105 1≤M≤106

输入样例：

3
aba
5
ababa

输出样例：

0 2

#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;

int n, m;
char p[N], s[M];
int ne[N]; // next有可能会报错

int main() {
  cin >> n >> p + 1 >> m >> s + 1; // 下标从1开始
  
  /* 求next过程 */
  for (int i = 2, j = 0; i <= n; i++) {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j++;
    ne[i] = j;
  }
  
  /* kmp匹配过程 */
  for (int i = 1, j = 0; i <= m; i++) {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j++;
    if (j == n) {
      printf("%d ", i - n);
      j = ne[j];
    }
  }
  return 0;
}

Trie树

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

---

维护一个字符串集合，支持两种操作：

1. I x 向集合中插入一个字符串 x；
2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗104

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

#include <iostream>
using namespace std;
const int N = 100010;

/* son数组为节点，cnt记录每个单词出现次数，下标是0的点，既是根节点，又是空节点 */
int son[N][26], cnt[N], idx;
char str[N];

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;
  scanf("%d", &n);
  while (n--) {
    char op[2];
    scanf("%s%s", op, str);
    if (op[0] == 'I') insert(str);
    else printf("%d\n", query(str));
  }
  
  return 0;
}

并查集

1. 将两个集合合并
2. 询问两个元素是否在一个集合中
3. 基本原理：每个集合用一棵树来表示，树根的编号就是整个集合的编号，每个节点储存他的父节点。
4. 优化：路经压缩（按秩合并）祥见CS61B

---

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

1. M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤105

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int p[N];

/* 返回x的根节点+路经压缩 */
int find(int x) {
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) p[i] = i;
  
  while (m--) {3
    char op[2];
    int a, b;
    /* scanf在读取字符串时会过滤空格和回车 */
    scanf("%s%d%d", op, &a, &b);
    
    if (op[0] == 'M') p[find(a)] = find(b);
    else {
      if (find(a) == find(b)) puts("Yes");
      else puts("No");
    }
  }
  return 0;
}

例：连通块中点的数量

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤105

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int p[N], s[N]; // s数组用于记录元素数量

int find(int x) {
  if (p[x] != x) p[x] = find(p[x]);
  return p[x];
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    s[i] = 1;
  }
  
  while (m--) {
    char op[5];
    int a, b;
    scanf("%s", op);
    
    if (op[0] == 'C') {
      scanf("%d%d", &a, &b);
      if (find(a) == find(b)) continue;
      s[find(b)] += s[find(a)];
      p[find(a)] = find(b);
    } else if (op[1] == '1') {
      scanf("%d%d", &a, &b);
      if (find(a) == find(b)) puts("Yes");
      else puts("No");
    } else {
      scanf("%d", &a);
      printf("%d\n", s[find(a)]);
    }
  }
  return 0;
}

堆排序

如何手写一个堆

1. 插入一个数
2. 求集合当中的最小值
3. 删除最小值
4. 删除任意一个元素（STL无法直接实现）
5. 修改任意一个元素（STL无法直接实现）

---

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

输出格式

共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围

1≤m≤n≤105， 1≤数列中元素≤109

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;

int n, m;
int h[N], s;

/* down函数递归构建 */
void down(int u) {
  int t = u;
  if (u * 2 <= s && h[u * 2] < h[t]) t = u * 2;
  if (u * 2 + 1 <= s && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
  if (u != t) {
    swap(h[u], h[t]);
    down(t);
  }
}

/* up函数循环构建即可 */
void up(int u) {
  while (u / 2 && h[u / 2] > h[u]) {
    swap(h[u / 2], h[u]);
    u /= 2;
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i<= n; i++) scanf("%d", &h[i]);
  s = n;
  
  for (int i = n / 2; i; i--) down(i); // 该建堆方式的时间复杂度为O(n) 可用数列证明
  while (m--) {
    printf("%d ", h[1]);
    h[1] = h[s--];
    down(1);
  }
}

例：模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：

1. I x，插入一个数 x；
2. PM，输出当前集合中的最小值；
3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
4. D k，删除第 k 个插入的数；
5. C k x，修改第 k 个插入的数，将其变为 x；

现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。

输入格式

第一行包含整数 N。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

1≤N≤105 −109≤x≤109 数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

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

int h[N], ph[N], hp[N], s;  // ph[k]储存第k个插入的点为堆中的哪个点，hp相反

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 <= s && h[u * 2] < h[t]) t = u * 2;
  if (u * 2 + 1 <= s && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
  if (u != t) {
    heap_swap(u, t);
    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, m = 0;
  scanf("%d", &n);
  while (n--) {
    char op[10];
    int k, x;
    scanf("%s", op);
    if (!strcmp(op, "I")) {
      scanf("%d", &x);
      s++;
      m++;
      ph[m] = s, hp[s] = m;
      h[s] = x;
      up(s);
    } else if (!strcmp(op, "PM"))
      printf("%d\n", h[1]);
    else if (!strcmp(op, "DM")) {
      heap_swap(1, s);
      s--;
      down(1);
    } else if (!strcmp(op, "D")) {
      scanf("%d", &k);
      k = ph[k];
      heap_swap(k, s);
      s--;
      down(k), up(k);
    } else {
      scanf("%d%d", &k, &x);
      k = ph[k];
      h[k] = x;
      down(k), up(k);
    }
  }
  return 0;
}

哈希表

存储结构：开放寻址法、拉链法

---

拉链法

维护一个集合，支持如下几种操作：

1. I x，插入一个整数 x；
2. Q x，询问整数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤N≤105 −109≤x≤109

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003; // 大于100000的第一个质数，保证重复的概率小

int h[N], e[N], ne[N], idx;

void insert(int x) {
  int k = (x % N + N) % N; // 保证余数为正数
  
  e[idx] = x; // 单链表
  ne[idx] = h[k];
  h[k] = idx++;
}

bool find(int x) {
  int k = (x % N + N) % N;
  for (int i = h[k]; i != -1; i = ne[i])
    if (e[i] == x) return true;
  return false;
}

int main() {
  int n;
  scanf("%d", &n);
  
  memset(h, -1, sizeof(h));
  
  while (n--) {
    char op[2];
    int x;
    scanf("%s%d", op, &x);
    
    if (*op == 'I') insert(x);
    else {
      if (find(x)) puts("Yes");
      else puts("No");
    }
  }
  return 0;
}

开放寻址法

#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, na = 0x3f3f3f3f;

int h[N];

int find(int x) {
  int k = (x % N + N) % N;
  
  while (h[k] != na && h[k] != x) {
    k++;
    if (k == N) k = 0;
  }
  return k;
}

int main() {
  int n;
  scanf("%d", &n);
  
  memset(h, 0x3f, sizeof(h)); // memset函数按字节
  
  while (n--) {
    char op[2];
    int x;
    scanf("%s%d", op, &x);
    int k = find(x);
    
    if (*op == 'I') h[k] = x;
    else {
      if (h[k] != na) puts("Yes");
      else puts("No");
    }
  }
  return 0;
}

字符串前缀哈希法

基本思想：将字符串等价为一个P进制的数，之后再模Q

注意：1. 不能映射为0 2. 不存在冲突

一般P取131或13331，Q取2⁶⁴

用途：快速判断字符串相等

---

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤105

输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r) {
  return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
  scanf("%d%d%s", &n, &m, str + 1);
  
  p[0] = 1;
  for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + str[i];
  }
  
  while (m--) {
    int l1, r1, l2, r2;
    scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
    if (get(l1, r1) == get(l2, r2)) puts("Yes");
    else puts("No");
  }
  return 0;
}

例题

最大异或对

在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1～AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤105, 0≤Ai<231

输入样例：

3
1 2 3

输出样例：

3

#include <iostream>
using namespace std;
const int N = 100010, M = 31 * N;

int n;
int a[N];
int 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;
    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() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  
  int res = 0;
  for (int i = 0; i < n; i++) {
    insert(a[i]); // 先插入防止空集特判
    int t = query(a[i]);
    res = max(res, a[i] ^ t);
  }
  
  printf("%d\n", res);
  
  return 0;
}

食物链（带权并查集）

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。

A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1∼N 编号。

每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 X 和 Y 是同类。

第二种说法是 2 X Y，表示 X 吃 Y。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 X 或 Y 比 N 大，就是假话；
3. 当前的话表示 X 吃 X，就是假话。

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入格式

第一行是两个整数 N 和 K，以一个空格分隔。

以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。

若 D=1，则表示 X 和 Y 是同类。

若 D=2，则表示 X 吃 Y。

输出格式

只有一个整数，表示假话的数目。

数据范围

1≤N≤50000, 0≤K≤100000

输入样例：

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

输出样例：

3

#include <iostream>
using namespace std;
const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x) {
  if (p[x] != x) {
    int t = find(p[x]);
    d[x] += d[p[x]];
    p[x] = t;
  }
  return p[x];
}

int main() {
  scanf("%d%d", &n, &m);
  
  for (int i = 0; i < n ; i++) p[i] = i;
  
  int res = 0;
  while (m--) {
    int t, x, y;
    scanf("%d%d%d", &t, &x, &y);
    
    if (x > n || y > n) res++;
    else {
      int px = find(x), py = find(y);
      if(t == 1) {
        if (px == py && (d[x] - d[y]) % 3) res++;
        else if (px != py) {
          p[px] = py;
          d[px] = d[y] - d[x];
        }
      } else {
        if (px == py && (d[x] - d[y] - 1) % 3) res++;
        else if (px != py) {
          p[px] = py;
          d[px] = d[y] + 1 - d[x];
        }
      }
    }
  }
  printf("%d\n", res);
  return 0;
}