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
",cnt);
35         }
36     }
37     return 0;
38 }

View Code

线段树代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 10000005;
 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].tot = 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 = 0;
28         if(tree[root].left != tree[root].right) {
29             tree[root<<1].mark = tree[root<<1|1].mark = 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     int a, b;
66     a = cal(root << 1, left, right);
67     b = cal(root << 1 | 1, left, right);
68     return a + b;
69 }
70 
71 int main() {
72     int t;
73     int n, m;
74     int a, b;
75     scanf("%d",&t);
76     while(t--) {
77         scanf("%d %d",&n, &m);
78         creat(1, 1, n);
79         for(int i = 1; i <= m; i++) {
80             scanf("%d %d",&a, &b);
81             printf("%d
", cal(1, a, b) );
82             update(1, a, b);
83         }
84     }
85     return 0;
86 }

View Code