「JOISC 2017 Day 1」港口设施

发表于
https://loj.ac/problem/2391

题目链接

「JOISC 2017 Day 1」港口设施

做法

考虑两个箱子如果进出栈时间呈嵌套关系，则这两个箱子就不能在同一个栈中。
考虑对于这种嵌套关系的两个箱子连一条边，最后的图中的二分图的方案数即总方案数。
如果暴力连边，那么边数可达 $ n^2 $ 个，显然过不去。
观察我们目前的连边方案：对于一个物品 $ u $ ，它会和之前物品序列中一段连续的物品 $ v1, v2, \dots, vk $ 连边。此时 $ v1, v2, \dots, vk $ 都是连通且同色的。
那么如果下一轮的连边的范围和 $ v1, v2, \dots, vk $ 有交，那么由连通性，这些边其实只连一条就够了。
具体地，对于每个左端点，我们对其维护一个 $ nxt $ ，表示如果现在再对它进行连边，应该跳到哪里。这样连边的数量就会减少很多，且不改变二分性和连通性。
最后 $ dfs $ 染色即可。时间复杂度 $ 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
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2000010;
int n, a[N], b[N], ar[N], ans = 1, fa1[N], fa2[N], nxt[N];
int clr[N];
vector<int> e[N];

int find(int *fa, int x) { return fa[x] == x ? x : fa[x] = find(fa, fa[x]); }
void dfs(int u) {
	for(auto v : e[u]) {
		if(clr[v] == -1) clr[v] = clr[u] ^ 1, dfs(v);
		if(clr[v] == clr[u]) { puts("0"); exit(0); }
	}
}
int main() {
	scanf("%d", &n), ans = 1;
	rep(i, 1, n + n + 1) fa1[i] = fa2[i] = i;
	rep(i, 1, n) {
		scanf("%d%d", &a[i], &b[i]), clr[i] = -1;
		ar[a[i]] = ar[b[i]] = i, fa1[b[i]] = b[i] + 1;
	}
	rep(i, 1, n + n) if(b[ar[i]] == i) {
		int lst = 0;
		for(int j = find(fa1, a[ar[i]] + 1); j <= i; j = find(fa1, j + 1)) {
			j = find(fa2, j), e[ar[i]].pb(ar[j]), e[ar[j]].pb(ar[i]);
			if(lst) fa2[lst] = j; lst = j;
		}
		fa1[a[ar[i]]] = a[ar[i]] + 1;
	}
	rep(i, 1, n) if(clr[i] == -1) clr[i] = 0, dfs(i), ans = ans * 2 % mod;
	printf("%d\n", ans);
	return 0;
}