Fork me on GitHub

[LA-4730] Kingdom 并查集+线段树

发表于 | 分类于
字数统计: 1,233字 | 阅读时长 ≈ 7分钟

题面

传送门:LA-4730

题目大意：

There were N cities in an ancient kingdom. In the beginning of the kingdom, all cities were isolated. Kings ordered their subjects to construct roads connecting cities. A lot of roads were built with time. Every road was always constructed along the line segment between two cities. All cities are partitioned into disjoint components of cities by road-connectivity. A connected component of cities was called a state. A state consists of cities and roads connecting them.

A historical record tells a time sequence of road constructions in order. A road connecting two citiesA and B doesn’t intersect with other roads at a point except forA and B. Before construction,A and B may have belonged to the same state or different states. After construction,A and B would belong to a same state, i.e., two states would merge into a state if needed.

Prof. Kim, a historian, is concerned about the following question: How many states does a horizontal line (corresponding to the latitude of a specific place) pass by at a moment of the past? The figure below shows an example of a configuration of roads at some moment. A circle represents a city and a line segment represents a road between two cities. There are 3 states. A line with y = 4.5 passes by two states with total 8 cities and a line with y = 6.5 passes by one state with 5 cities.

（逃

正经：

平面上有n个城市，初始时城市之间没有任何双向道路相连。你的任务是一次执行以下指令。

road A B：在城市A和B之间连一条双向道路，保证这条道路不和其他道路在非端点处相交。

line C：询问一条Y=C的水平线和多少个州相交，以及这些州一共包含多少座城市。

思路

看到包含多少城市想到并查集。这里如果单个枚举的话很费时间会T飞

我们就用线段树来维护区间内的城市数量和州的数量。

发现其实这题与x轴上的大小值没有任何关系。

只要考虑y轴坐标的上下最值即可

注意分类讨论。

以及并查集的时候别忘记 路径压缩

线段树update别写炸

就A了

代码

3617啊珂怕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;
#define lc rt<<1
#define rc rt<<1|1
const int maxn = 1e5+5; 
int miny[maxn],maxy[maxn],n,m,fa[maxn],d[maxn];
int getf(int x){return x == fa[x] ? x : fa[x] = getf(fa[x]);}
inline void read(int &x)
{
	x=0;char ch=getchar();int f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
struct SegmentTree{
	int sum1[maxn<<2],sum2[maxn<<2];
	int lazy1[maxn<<2],lazy2[maxn<<2];
	void Pushup(int rt)
	{
		sum1[rt] = sum1[rc] + sum1[lc];
		sum2[rt] = sum2[rc] + sum2[lc];	
	} 
	void Pushdown(int rt)
	{
		if (lazy1[rt])
		{
			sum1[lc] += lazy1[rt];
			sum2[rc] += lazy1[rt];
			lazy1[lc] += lazy1[rt];
			lazy1[rc] += lazy1[rt];
			lazy1[rt] = 0;	
		} 
		if (lazy2[rt])
		{
			sum1[lc] += lazy2[rt];
			sum2[rc] += lazy2[rt];
			lazy2[lc] += lazy2[rt];
			lazy2[rc] += lazy2[rt];
			lazy2[rt] = 0;	
		} 
	}
	void update(int rt,int l,int r,int L,int R,int x,int f)
	{
		if (L > R) return ;
		if(L <= l && R >= r)
		{
			if(!f)
			{
				lazy1[rt] += x;
				sum1[rt] += x;
			}
			else
			{
				lazy2[rt] += x;
				sum2[rt] += x;
			}
			return ;
		} 
		Pushdown(rt);
		int m = (l+r) >> 1;
		if (l <= m) update(lc,l,m,L,R,x,f);
		if (r > m) update(rc,m+1,r,L,R,x,f);
		Pushup(rt);
	}
	int query(int rt,int l,int r,int c)
	{
		if (l == r) return rt;
		Pushdown(rt);
		int m = (l+r) >> 1;
		if (c <= m) return query(lc,l,m,c);
		else Pushup(rt);
	}
}Tree;
inline void set_init()
{
	memset(miny,0,sizeof(miny));
	memset(maxy,0,sizeof(maxy));
	memset(Tree.lazy1,0,sizeof(Tree.lazy1));
	memset(Tree.sum1,0,sizeof(Tree.sum1));
	memset(Tree.lazy2,0,sizeof(Tree.lazy2));
	memset(Tree.sum2,0,sizeof(Tree.sum2));
	for (int i = 1; i <= n; i++)
	fa[i] = i;
	memset(d,1,sizeof(d));
}
int main(int argc, char *argv[])
{
	int T,Lim;
	int x,y;double c;
	char opt[13];
	read(T);
	while(T--)
	{
		Lim = -0x7fffffff;
		read(n);
		set_init(); 
		for (int i = 1; i <= n; i++)
		{
			int t1,t2;
			read(t1),read(t2);
			miny[i] = maxy[i] = t2;
			Lim = max(Lim,t2);
		}
		Lim++;
		read(m);
		while(m--)
		{
			scanf("%s",&opt);
			if(opt[0] == 'r')
			{
				read(x);read(y);
				int px = getf(x),py = getf(y);
				if(px == py) ;
				else
				{
					if (maxy[px] > maxy[py])
					swap(px,py);
					if (miny[py] > maxy[px]) {
                        Tree.update(1, 1, Lim, maxy[px] + 1, miny[py], 1, 0);
                        Tree.update(1, 1, Lim, maxy[px] + 1, miny[py], d[px] + d[py], 1);
                        Tree.update(1, 1, Lim, miny[px] + 1, maxy[px], d[py], 1);
                        Tree.update(1, 1, Lim, miny[py] + 1, maxy[py], d[px], 1);
                    }
                    else if (miny[px] > miny[py]) {
                        Tree.update(1, 1, Lim, miny[px] + 1, maxy[px], -1, 0);
                        Tree.update(1, 1, Lim, miny[py] + 1, miny[px], d[px], 1);
                        Tree.update(1, 1, Lim, maxy[px] + 1, maxy[py], d[px], 1);
                    }
                    else {
                        Tree.update(1, 1, Lim, miny[py] + 1, maxy[px], -1, 0);
                        Tree.update(1, 1, Lim, miny[px] + 1, miny[py], d[py], 1);
                        Tree.update(1, 1, Lim, maxy[px] + 1, maxy[py], d[px], 1);
                    }
                    fa[px] = py;
                    d[py] += d[px];
                    miny[py] = min(miny[py], miny[px]);
                    maxy[py] = max(maxy[py], maxy[px]);
                }		
			} 
			else
			{
				scanf("%lf",&c);
				int k = Tree.query(1,1,Lim,(int)(c+1));
				printf("%d %d\n",Tree.sum1[k],Tree.sum2[k]);
			}
		}
	}
	return 0;
}