文创产品设计网站推荐,网站切图怎么切,百度网址大全网址导航大全,北京网梯科技发展有限公司并查集、树状数组、线段树 并查集树状数组树状数组1 (单点修改#xff0c;区间查询)树状数组2 (单点查询#xff0c;区间修改) 并查集
【模板】并查集
题目描述
如题#xff0c;现在有一个并查集#xff0c;你需要完成合并和查询操作。
输入格式
第一行包含两个整数 … 并查集、树状数组、线段树 并查集树状数组树状数组1 (单点修改区间查询)树状数组2 (单点查询区间修改) 并查集
【模板】并查集
题目描述
如题现在有一个并查集你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N , M N,M N,M ,表示共有 N N N 个元素和 M M M 个操作。
接下来 M M M 行每行包含三个整数 Z i , X i , Y i Z_i,X_i,Y_i Zi,Xi,Yi 。
当 Z i 1 Z_i1 Zi1 时将 X i X_i Xi 与 Y i Y_i Yi 所在的集合合并。
当 Z i 2 Z_i2 Zi2 时输出 X i X_i Xi 与 Y i Y_i Yi 是否在同一集合内是的输出 Y 否则输出 N 。
输出格式
对于每一个 Z i 2 Z_i2 Zi2 的操作都有一行输出每行包含一个大写字母为 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 % 30\% 30% 的数据 N ≤ 10 N \le 10 N≤10 M ≤ 20 M \le 20 M≤20。
对于 70 % 70\% 70% 的数据 N ≤ 100 N \le 100 N≤100 M ≤ 1 0 3 M \le 10^3 M≤103。
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 1 0 4 1\le N \le 10^4 1≤N≤104 1 ≤ M ≤ 2 × 1 0 5 1\le M \le 2\times 10^5 1≤M≤2×105 1 ≤ X i , Y i ≤ N 1 \le X_i, Y_i \le N 1≤Xi,Yi≤N Z i ∈ { 1 , 2 } Z_i \in \{ 1, 2 \} Zi∈{1,2}。
以下是模板代码
#includebits/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 x x 求出某区间每一个数的和
输入格式
第一行包含两个正整数 n , m n,m n,m分别表示该数列数字的个数和操作的总个数。
第二行包含 n n n 个用空格分隔的整数其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 m m m 行每行包含 3 3 3 个整数表示一个操作具体如下 1 x k 含义将第 x x x 个数加上 k k k 2 x y 含义输出区间 [ x , y ] [x,y] [x,y] 内每个数的和
输出格式
输出包含若干行整数即为所有操作 2 2 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 % 30\% 30% 的数据 1 ≤ n ≤ 8 1 \le n \le 8 1≤n≤8 1 ≤ m ≤ 10 1\le m \le 10 1≤m≤10 对于 70 % 70\% 70% 的数据 1 ≤ n , m ≤ 1 0 4 1\le n,m \le 10^4 1≤n,m≤104 对于 100 % 100\% 100% 的数据 1 ≤ n , m ≤ 5 × 1 0 5 1\le n,m \le 5\times 10^5 1≤n,m≤5×105。
数据保证对于任意时刻 a a a 的任意子区间包括长度为 1 1 1 和 n n n 的子区间和均在 [ − 2 31 , 2 31 ) [-2^{31}, 2^{31}) [−231,231) 范围内。
样例说明 故输出结果14、16
以下是模板代码
#includebits/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
题目描述
如题已知一个数列你需要进行下面两种操作 将某区间每一个数加上 x x x 求出某一个数的值。
输入格式
第一行包含两个整数 N N N、 M M M分别表示该数列数字的个数和操作的总个数。
第二行包含 N N N 个用空格分隔的整数其中第 i i i 个数字表示数列第 $i $ 项的初始值。
接下来 M M M 行每行包含 2 2 2 或 4 4 4个整数表示一个操作具体如下
操作 1 1 1 格式1 x y k 含义将区间 [ x , y ] [x,y] [x,y] 内每个数加上 k k k
操作 2 2 2 格式2 x 含义输出第 x x x 个数的值。
输出格式
输出包含若干行整数即为所有操作 2 2 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 % 30\% 30% 的数据 N ≤ 8 N\le8 N≤8 M ≤ 10 M\le10 M≤10
对于 70 % 70\% 70% 的数据 N ≤ 10000 N\le 10000 N≤10000 M ≤ 10000 M\le10000 M≤10000
对于 100 % 100\% 100% 的数据 1 ≤ N , M ≤ 500000 1 \leq N, M\le 500000 1≤N,M≤500000 1 ≤ x , y ≤ n 1 \leq x, y \leq n 1≤x,y≤n保证任意时刻序列中任意元素的绝对值都不大于 2 30 2^{30} 230。
以下是模板代码
#includebits/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); // 将区间[y1, n]的值减去k保持区间[x, y]加上k} else {int x;cin x; // 输入要查询的位置xcout sum(x) endl; // 输出第x个数的值}}return 0;
}
