Loj 6698 一键挖矿

Posted on | Views:

线段树.

一维时是经典问题,但我们常用的单调栈 + 线段树做法并不能比较方便的搬到二维上,需要考虑另外一种条件转化.

加入权值在区间 $[l,r]$ 内的格子,令它们的颜色为黑色,其它的格子颜色为白色.

考虑所有的 $(n+1)\times (m+1)$ 个 $2\times 2$ 的小正方形(超出边界也算),则所有黑色格子形成一个矩形,当且仅当恰好有 $4$ 个小正方形内部有 $1$ 个黑色格子,并且没有任何一个小正方形内部有 $3$ 个黑色格子.

必要性是显然的,任何一个由黑色格子组成的矩形都满足以上条件.充分性可以这样考虑,初始时一定是有 $4$ 个黑色格子,要求恰好有 $4$ 个小正方形内部有 $1$ 个黑色格子,就必须用黑色格子将它们连起来,形成矩形的边界,而此时角的地方会出现包含 $3$ 个黑色格子的小正方形,只有将内部全部填满后才会消失,于是可以得出这个条件是充分必要的.

有了这个结论,再来考虑如何计算答案.我们从小到大枚举 $r$ ,并对每个 $l\le r$ 维护 $f(l)$ ,表示将权值在 $[l,r]$ 内的格子染黑后,有多少个小正方形内部有 $1$ 个或 $3$ 个黑色格子.不难发现 $f(l)\ge 4,f(r)=4$ 是恒成立的,根据上面的结论,我们只需要求有多少个 $f(l)=4$ ,即最小值的个数.

用线段树维护 $f$ 以及最小值个数,每次 $r$ 增加 $1$ 时,会影响到周边的 $4$ 个 $2\times 2$ 的小正方形,在线段树上区间加即可.

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

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
150
//%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 N = 2e5 + 10;
int n, m, mx;
vector<int> w[N];
int tag[N << 2];
struct info
{
	int mi, cnt;
} tree[N << 2];
info operator + (const info &A, const info &B)
{
	if (A.mi == B.mi)
		return (info){A.mi, A.cnt + B.cnt};
	else if (A.mi < B.mi)
		return A;
	return B;
}
void pushup(int x)
{
	tree[x] = tree[x << 1] + tree[x << 1 | 1];
} 
void BuildTree(int x, int l, int r)
{
	if (l == r)
	{
		tree[x] = (info){0, 1};
		return;
	}
	int mid = (l + r) >> 1;
	BuildTree(x << 1, l, mid);
	BuildTree(x << 1 | 1, mid + 1, r);
	pushup(x);
}
void modify(int x, int c)
{
	tree[x].mi += c;
	tag[x] += c;
}
void pushdown(int x)
{
	if (tag[x])
	{
		modify(x << 1, tag[x]);
		modify(x << 1 | 1, tag[x]);
		tag[x] = 0;
	}
}
void upd(int x, int l, int r, int L, int R, int c)
{
	if (L > R)
		return;
	if (L <= l && r <= R)
		return modify(x, c);
	int mid = (l + r) >> 1;
	pushdown(x);
	if (L <= mid)
		upd(x << 1, l, mid, L, R, c);
	if (R > mid)
		upd(x << 1 | 1, mid + 1, r, L, R, c);
	pushup(x);
}
void query(info &res, int x, int l, int r, int L, int R)
{
	if (L <= l && r <= R)
	{
		res = res + tree[x];
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid)
		query(res, x << 1, l, mid, L, R);
	if (R > mid)
		query(res, x << 1 | 1, mid + 1, r, L, R);
}
int f(int x)
{
	return x == 1 || x == 3;
}
void solve(int x, int x0, int x1, int x2)
{
	int a[5] = {0, x, x0, x1, x2};
	sort(a + 1, a + 1 + 4);
	int p = lower_bound(a + 1, a + 1 + 4, x) - a;
	for (int i = 1; i <= p; ++i)
	{
		int t = f(p - i + 1) - f(p - i);
		upd(1, 1, mx, a[i - 1] + 1, a[i], t);
	}
}
int px[N], py[N];
int main()
{
	n = read(), m = read(), mx = n * m;
	BuildTree(1, 1, mx);
	for (int i = 0; i <= n + 1; ++i)
	{
		w[i].resize(m + 2);
		w[i][0] = w[i][m + 1] = mx + 1;
		for (int j = 1; j <= m; ++j)
			if (i == 0 || i == n + 1)
				w[i][j] = mx + 1;
			else
			{
				w[i][j] = read();
				px[w[i][j]] = i, py[w[i][j]] = j;
			}	
	}
	ll ans = 0;
	for (int r = 1; r <= mx; ++r)
	{
		int x = px[r], y = py[r];
		solve(w[x][y], w[x - 1][y], w[x][y - 1], w[x - 1][y - 1]);
		solve(w[x][y], w[x - 1][y], w[x][y + 1], w[x - 1][y + 1]);
		solve(w[x][y], w[x + 1][y], w[x][y - 1], w[x + 1][y - 1]);
		solve(w[x][y], w[x + 1][y], w[x][y + 1], w[x + 1][y + 1]);
		info tmp{4, 0};
		query(tmp, 1, 1, mx, 1, r);
		ans += tmp.cnt;
	}
	cout << ans << '\n';
	return 0;
}