并查集

【模板】并查集

題目描述

如題，現在有一個并查集，你需要完成合并和查詢操作。

輸入格式

第一行包含兩個整數 $N,M$ ,表示共有 $N$ 個元素和 $M$ 個操作。

接下來 $M$ 行，每行包含三個整數 $Z_i,X_i,Y_i$ 。

當 $Z_i=1$ 時，將 $X_i$ 與 $Y_i$ 所在的集合合并。

當 $Z_i=2$ 時，輸出 $X_i$ 與 $Y_i$ 是否在同一集合內，是的輸出
Y ；否則輸出 N 。

輸出格式

對于每一個 $Z_i=2$ 的操作，都有一行輸出，每行包含一個大寫字母，為 Y 或者 N 。

樣例輸入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

樣例輸出 #1

N
Y
N
Y

提示

對于 $30\%$ 的數據，$N\le 10$，$M\le 20$。

對于 $70\%$ 的數據，$N\le 100$，$M\le 10^3$。

對于 $100\%$ 的數據，$1\le N\le 10^4$，$1\le M\le 2\times 10^5$，$1\le X_i,Y_i\le N$， Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi?∈{1,2}。

以下是模板代碼

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10005int fa[MAXN]; // 用于存儲每個元素所屬的集合的根節點// 查找操作，返回元素x所屬集合的根節點
int find(int x) {if(x == fa[x]) return x; // 如果當前節點是根節點，直接返回return fa[x] = find(fa[x]); // 路徑壓縮，將x的父節點直接設為根節點，加快以后的查找
}// 合并操作，將兩個集合合并
void join(int c1, int c2) {int f1 = find(c1); // 查找c1所屬的集合的根節點int f2 = find(c2); // 查找c2所屬的集合的根節點if(f1 != f2) // 如果根節點不同，表示c1和c2不在同一集合中fa[f1] = f2; // 將c1的根節點的父節點設為c2的根節點，即合并兩個集合
}int main() {int n, m;cin >> n >> m; // 輸入元素個數n和操作個數mfor(int i = 1; i <= n; i++) fa[i] = i; // 初始化，每個元素初始時都是一個單獨的集合，根節點就是自己while(m--) {int z, x, y;cin >> z >> x >> y; // 輸入操作類型z以及兩個元素x和yif(z == 1) {join(x, y); // 合并操作，將x和y所在的集合合并} else {if(find(x) == find(y))cout << "Y" << endl; // 查找操作，如果x和y在同一個集合中，輸出Yelsecout << "N" << endl; // 否則輸出N}}return 0;
}

樹狀數組

樹狀數組1 (單點修改，區間查詢)

【模板】樹狀數組 1

題目描述

如題，已知一個數列，你需要進行下面兩種操作：

• 將某一個數加上 $x$

• 求出某區間每一個數的和

輸入格式

第一行包含兩個正整數 $n,m$，分別表示該數列數字的個數和操作的總個數。

第二行包含 $n$ 個用空格分隔的整數，其中第 $i$ 個數字表示數列第 $i$ 項的初始值。

接下來 $m$ 行每行包含 $3$ 個整數，表示一個操作，具體如下：

• 1 x k 含義：將第 $x$ 個數加上 $k$

• 2 x y 含義：輸出區間 $[x,y]$ 內每個數的和

輸出格式

輸出包含若干行整數，即為所有操作 $2$ 的結果。

樣例輸入 #1

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

樣例輸出 #1

14
16

提示

【數據范圍】

對于 $30\%$ 的數據，$1\le n\le 8$，$1\le m\le 10$；
對于 $70\%$ 的數據，$1\le n,m\le 10^4$；
對于 $100\%$ 的數據，$1\le n,m\le 5\times 10^5$。

數據保證對于任意時刻，$a$ 的任意子區間（包括長度為 $1$ 和 $n$ 的子區間）和均在 $[?2^{31},2^{31})$ 范圍內。

樣例說明：

故輸出結果14、16

以下是模板代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
#define lowbit(x) ((x) & (-x))
int tree[N] = {0}; // 樹狀數組void update(int x, int d) { // 單點修改：修改元素 a[x]，a[x] = a[x] + dwhile (x <= N) {tree[x] += d; // 將當前位置的值增加dx += lowbit(x); // 轉到下一個需要修改的位置}
}int sum(int x) { // 查詢前綴和：返回前綴和 sum = a[1] + a[2] + ... + a[x]int ans = 0;while (x > 0) {ans += tree[x]; // 累加當前位置的值x -= lowbit(x); // 轉到前一個位置}return ans;
}int main() {int n, m, a;cin >> n >> m; // 輸入數列數字個數n和操作總個數mfor (int i = 1; i <= n; i++) {cin >> a; // 輸入每個數列項的初始值update(i, a); // 初始化計算tree[]數組}while (m--) {int op;cin >> op; // 輸入操作類型if (op == 1) {int x, k;cin >> x >> k; // 輸入要修改的元素位置x和要加的值kupdate(x, k); // 對位置x的元素進行加法操作} else {int x, y;cin >> x >> y; // 輸入查詢區間[x, y]cout << sum(y) - sum(x - 1) << endl; // 輸出區間內元素和}}return 0;
}

樹狀數組2 (單點查詢，區間修改)

【模板】樹狀數組 2

題目描述

如題，已知一個數列，你需要進行下面兩種操作：

1. 將某區間每一個數加上 $x$；

2. 求出某一個數的值。

輸入格式

第一行包含兩個整數 $N$、$M$，分別表示該數列數字的個數和操作的總個數。

第二行包含 $N$ 個用空格分隔的整數，其中第 $i$ 個數字表示數列第 $i $ 項的初始值。

接下來 $M$ 行每行包含 $2$ 或 $4$個整數，表示一個操作，具體如下：

操作 $1$： 格式：1 x y k 含義：將區間 $[x,y]$ 內每個數加上 $k$；

操作 $2$： 格式：2 x 含義：輸出第 $x$ 個數的值。

輸出格式

輸出包含若干行整數，即為所有操作 $2$ 的結果。

樣例輸入 #1

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

樣例輸出 #1

6
10

提示

樣例 1 解釋：

故輸出結果為 6、10。

---

數據規模與約定

對于 $30\%$ 的數據：$N\le 8$，$M\le 10$；

對于 $70\%$ 的數據：$N\le 10000$，$M\le 10000$；

對于 $100\%$ 的數據：$1\le N,M\le 500000$，$1\le x,y\le n$，保證任意時刻序列中任意元素的絕對值都不大于 $2^{30}$。

以下是模板代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
#define lowbit(x) ((x) & (-x))
int tree[N] = {0}; // 樹狀數組void update(int x, int d) { // 單點修改：修改元素 a[x]，a[x] = a[x] + dwhile (x <= N) {tree[x] += d; // 將當前位置的值增加dx += lowbit(x); // 轉到下一個需要修改的位置}
}int sum(int x) { // 查詢前綴和：返回前綴和 sum = a[1] + a[2] + ... + a[x]int ans = 0;while (x > 0) {ans += tree[x]; // 累加當前位置的值x -= lowbit(x); // 轉到前一個位置}return ans;
}int main() {int n, m;int old = 0, a;cin >> n >> m; // 輸入數列數字個數n和操作總個數mfor (int i = 1; i <= n; i++) {cin >> a; // 輸入每個數列項的初始值update(i, a - old); // 初始化計算tree[]數組,這里是一個差分數組old = a;}while (m--) {int op;cin >> op; // 輸入操作類型if (op == 1) {int x, y, k;cin >> x >> y >> k; // 輸入要修改的區間[x, y]和要加的值kupdate(x, k);update(y + 1, -k); // 將區間[y+1, n]的值減去k，保持區間[x, y]加上k} else {int x;cin >> x; // 輸入要查詢的位置xcout << sum(x) << endl; // 輸出第x個數的值}}return 0;
}