Falling Sand (Hard Version)

题目链接：luogu CF1534F2

题目大意

给你一个网格，每个位置可能有沙子。
如果你操作了一个沙子，它会下落，并且操作它下落过程中上下左右相邻的沙子。
然后问你最少要自己操作多少个沙子才会使得所有沙子都被操作。

思路

首先一些贪心，就是肯定是点一列的最上面，然后能影响的肯定是一个区间。（就算中间隔开了你点中间还是会影响被隔开的，所以可以算不影响）
（然后被影响的也是一个区间）

考虑模拟这个过程，那就是如果一个沙子会影响到另一个沙子，就连边。
然后你就可以通过 dfs，得到一个沙子被操作的区间。
（找左边界就从左到右搜索，否则从右到左搜索得到右边界）

然后剩下就是一个区间覆盖问题，随便用啥都行。

代码

#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f3f3f3f3f
#define bh(x, y) (((x) - 1) * n + (y))

using namespace std;

const int N = 4e5 + 100;
int n, m, L[N], R[N], nd[N], Rs[N], sta[N], f[N];
char c;
vector <int> a[N], up[N];
struct node {
	int to, nxt;
}e[N << 3];
int le[N], KK;
bool in[N];

void add(int x, int y) {e[++KK] = (node){y, le[x]}; le[x] = KK;} 

void dfsl(int now, int col) {
	L[now] = col; in[now] = 1;
	for (int i = le[now]; i; i = e[i].nxt) if (!in[e[i].to]) dfsl(e[i].to, col);
}

void dfsr(int now, int col) {
	R[now] = col; in[now] = 1;
	for (int i = le[now]; i; i = e[i].nxt) if (!in[e[i].to]) dfsr(e[i].to, col);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			c = getchar(); while (c != '#' && c != '.') c = getchar();
			if (c == '#') a[j].push_back(n - i + 1);
		}
	for (int i = 1; i <= m; i++) reverse(a[i].begin(), a[i].end());
	for (int i = 1; i <= m; i++) scanf("%d", &nd[i]);
	
	for (int i = 1; i <= m; i++) {
		if (!a[i].size()) continue;
		for (int j = 1; j < a[i].size(); j++) {
			add(bh(i, a[i][j]), bh(i, a[i][j - 1]));
			if (a[i][j - 1] + 1 == a[i][j]) add(bh(i, a[i][j - 1]), bh(i, a[i][j]));
		}
		for (int op = 1; op >= -1; op--) { if (op == 0) continue;
			if (!a[i + op].size()) continue;
			int now = a[i + op].size() - 1; while (now >= 0 && a[i + op][now] > a[i][a[i].size() - 1]) now--;
			int nowx = a[i].size() - 1;
			for (int j = a[i][a[i].size() - 1]; j >= 1; j--) {
				if (nowx > 0 && a[i][nowx - 1] == j) nowx--;
				if (now >= 0 && a[i + op][now] == j) add(bh(i, a[i][nowx]), bh(i + op, a[i + op][now])), now--;
			}
		}
	}
	
	for (int i = 1; i <= m; i++)
		if (a[i].size() && !in[bh(i, a[i][a[i].size() - 1])])
			dfsl(bh(i, a[i][a[i].size() - 1]), i);
	memset(in, 0, sizeof(in));
	for (int i = m; i >= 1; i--)
		if (a[i].size() && !in[bh(i, a[i][a[i].size() - 1])])
			dfsr(bh(i, a[i][a[i].size() - 1]), i);
	
	for (int i = 1; i <= m; i++)
		for (int j = 0; j < nd[i]; j++)
			Rs[R[bh(i, a[i][j])]] = max(Rs[R[bh(i, a[i][j])]], L[bh(i, a[i][j])]);
	int l = 1, r = 1;
	for (int i = 1; i <= m; i++) {
		f[i] = f[sta[l]] + 1;
		while (l <= r && f[sta[r]] >= f[i]) r--;
		sta[++r] = i;
		while (l <= r && sta[l] < Rs[i]) l++;
	}
	printf("%d", f[sta[l]]);
	
	return 0;
} 
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