首页 > 代码库 > hlgChocolate Auction【并查集】
hlgChocolate Auction【并查集】
大意：
给你一个区间大小为100000000 然后每次查询一个区间之内有多少值未被标记并且把该区间之内的所有的未被标记的全部标记
查询次数为100000
分析：
这个题给我的第一感觉就是线段树但是线段树10^7的话开不下啊
然后并查集再一次发挥了它无穷大的力量
我们对于每个查询的区间
把其中所有的值都指向他能指向的最远的值
那么我们总的查找次数就可以控制在10^7之内
完美解决问题
说的有点抽象
用代码模拟一下你就会发现这个方法有多么的机智
我准备用线段树做一下
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 10000005; 7 8 int fa[maxn]; 9 10 int find(int x) {11 if(x == fa[x]) return x;12 return fa[x] = find(fa[x]);13 }14 15 int main() {16 int t;17 int n, m;18 int a, b;19 scanf("%d",&t);20 while(t--) {21 scanf("%d %d",&n, &m);22 for(int i = 0; i <= n + 3; i++) {23 fa[i] = i;24 }25 for(int i = 1; i <= m; i++) {26 scanf("%d %d",&a, &b);27 int p = find(a);28 int cnt = 0;29 while(p <= b) {30 cnt ++;31 fa[find(p)] = find(p + 1);32 p = find(p + 1);33 }34 printf("%d\n",cnt);35 }36 }37 return 0;38 }
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 1000005; 7 8 struct Node { 9 int left, right;10 int tot; 11 int mark;12 }tree[maxn << 2];13 14 int creat(int root, int left, int right) {15 tree[root].mark = 0;16 tree[root].left = left;17 tree[root].right = right;18 if(left == right) return tree[root].total = 1;19 int a, b, mid = (left + right) >> 1;20 a = creat(root << 1, left, mid);21 b = creat(root << 1 | 1, mid + 1, right);22 return tree[root].tot = a + b;23 }24 25 void update_mark(int root) {26 if(tree[root].mark) {27 tree[root].tot = tree[root].mark ;28 if(tree[root].left != tree[root].right) {29 tree[root<<1].left = tree[root<<1|1].right = tree[root].mark;30 }31 tree[root].mark = 0;32 }33 }34 35 int update(int root, int left, int right) {36 update_mark(root);37 38 if(tree[root].left > right || tree[root].right < left) {39 return tree[root].tot;40 }41 42 if(left <= tree[root].left && tree[root].right <= right) {43 tree[root].mark = 1;44 return tree[root].tot = 0;45 }46 47 int a, b;48 49 a = update(root << 1, left, right);50 b = update(root << 1 | 1, left, right);51 return tree[root].tot = a + b;52 }53 54 55 int cal(int root, int left, int right) {56 update_mark(root);57 58 if(tree[root].left > right || tree[root].right < left) {59 return 0;60 }61 62 if(tree[root].left >= left && tree[root].right <= right) {63 return tree[root].tot;64 }65 66 int a, b;67 68 a = cal(root << 1, a, b);69 b = cal(root << 1 | 1, a, b);70 return a + b;71 }72 73 int main() {74 int t;75 int n, m;76 int a, b;77 78 scanf("%d",&t);79 while(t--) {80 scanf("%d %d",&n, &m);81 creat(1, 1, n);82 for(int i = 1; i <= m; i++) {83 scanf("%d %d",&a, &b);84 printf("%d\n", cal(1, a, b) );85 update(1, a, b);86 }87 }88 return 0;89 }
hlgChocolate Auction【并查集】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。