Loj 2391 港口设施

Posted on | Views:

并查集 + 二分图染色.

把每个物品的进出时间看成一条线段,则被分在同一个栈中的两条线段不能相交,只能包含或相离.

把相交的物品之间连上边,方案数就等价于合法的二分图染色方案数.

若直接连边,边数是 $O(n^2)$ 的,考虑优化建图.

将所有点按照左端点从小到大排序,按照右端点从小到大依次考虑.

它能连的点应当是左端点在区间 $[1,l)$ 内,且还没有被考虑过的所有点.

注意到若两个点分别向 $[a,b],[c,d]$ 连边,且有 $a<c<b<d$ ,那么连边时可以将 $[c,d]$ 直接换成 $[b,d]$ .

因为 $[a,b],[c,d]$ 里面的点一定都是同色的,连 $[a,b]$ 时已经保证了 $[c,b]$ 内同色,只需要对 $[b,d]$ 连边即可.

用一个并查集维护每个点通过同色的点向右最大能拓展到的位置,直接从那个点开始连边即可.

时间复杂度 $O(n\log n)$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 1e9 + 7;
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 2e6 + 10;
int n, p[N], fa[N], nxt[N], vis[N], cnt = 0, col[N];
int Find(int x)
{
	return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
vector<int> G[N];
bool dfs(int x)
{
	for (int y : G[x])
		if (col[y] && col[x] + col[y] != 3)
			return false;
		else if (!col[y])
		{
			col[y] = 3 - col[x];
			bool f = dfs(y);
			if (!f)
				return false;
		}
	return true;
}
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
	{
		int l = read(), r = read();
		p[l] = p[r] = i;
	}
	iota(fa + 1, fa + 2 + n, 1);
	iota(nxt + 1, nxt + 2 + n, 1);
	for (int i = 1; i <= 2 * n; ++i) 
		if (!vis[p[i]]) // left endpoint, do counting sort
			vis[p[i]] = ++cnt;
		else // right endpoint, add edges
		{
			int id = vis[p[i]];
			fa[id] = Find(id + 1);
			for (int j = fa[id], t; j <= cnt; j = t)
			{
				G[id].push_back(j);
				G[j].push_back(id);
				t = Find(nxt[j] + 1);
				nxt[j] = cnt;
			}
		}
	int ans = 1;
	for (int i = 1; i <= n && ans; ++i)
		if (!col[i])
		{
			col[i] = 1;
			bool f = dfs(i);
			if (f)
				ans = mul(ans, 2);
			else
				ans = 0; 
		}
	write(ans, '\n');
	return 0;
}