$set$瞎搞

首先非常显然,一个矩形$(x1, y1, x2, y2)$的代价就是$\displaystyle\sum_{i = x1}^{x2}\sum_{j = y1}^{y2} h[i][j] - \min_{x1 \le i \le x2, y1 \le j \le y2} h[i][j]$,我们用$f[i][j]$表示以$(i, j)$为左上角的矩形的代价。即矩形$(i, j, i + a - 1, j + b - 1)$的代价。

我们首先考虑如何求出$f[i][j]$。

前面的求和可以一个二维前缀和简单解决,关键在于后面的$\min​$。

我们对每行都建一个$st​$表,考虑我们把当前我们要求的区间里的$h[i][j]​$都丢进一个$set​$中。

我们考虑每次把矩形往下移动。

发现其实对于每一行,只有它的在范围内的最小值才有贡献,所$set$中只需要放每行的最小值(可以用$st$表快速查询)。

我们再考虑如下图所示。

然后如果我们要从蓝色矩形移动到黑色矩形,那么我们只需要在$set$中删去灰色部分的最小值,再加入浅蓝色部分的最小值即可。

求出了$f[i][j]$之后就可以按题意模拟了w

每次我们可以找出$f[i][j]$的最小值,这个排遍序轻松解决(我之前作死用set被卡常了)然后给所有因为这个矩形被取到了导致不能取的打上标记,这样子时间复杂度是正确的,最多只会被取到$\frac{n m}{ab}$个矩形,然后每次打标记是$O(a * b)$的,最后复杂度就是$O(\frac{n m}{a b} a b) = O(n m)$的。

复杂度$O(n m \log n)$,轻微卡常w

代码

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
#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647

int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}

int f[1010][1010][12];
std::multiset<ll> s2;
int ans1[1000010], ans2[1000010], h[1010][1010];
ll ans3[1000010], sum[1010][1010], val[1010][1010];
bool used[1010][1010];
std::pair<int, int> s[1000010];

ll query(int x, int l, int r){
int lg = log2(r - l + 1);
return std::min(f[x][l][lg], f[x][r - (1 << lg) + 1][lg]);
}

bool cmp(std::pair<int, int> a, std::pair<int, int> b){
if(val[a.first][a.second] == val[b.first][b.second])
return a < b;
return val[a.first][a.second] < val[b.first][b.second];
}

int main(){
int n = inp();
int m = inp();
int a = inp();
int b = inp();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
f[i][j][0] = h[i][j] = inp();
for(int i = 1; i <= n; i++)
for(int u = 1; u <= 10; u++)
for(int j = 1; j <= m; j++)
if(j + (1 << u) - 1 <= m)
f[i][j][u] = std::min(f[i][j][u - 1], f[i][j + (1 << (u - 1))][u - 1]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + h[i][j];
for(int j = 1; j <= m - b + 1; j++){
s2.clear();
for(int i = 1; i <= a; i++)
s2.insert(query(i, j, j + b - 1));
for(int i = 1; i <= n - a + 1; i++){
val[i][j] = sum[i + a - 1][j + b - 1] + sum[i - 1][j - 1] - sum[i + a - 1][j - 1] - sum[i - 1][j + b - 1] - (*(s2.begin())) * (a * b);
s2.erase(s2.find(query(i, j, j + b - 1)));
if(i + a <= n)
s2.insert(query(i + a, j, j + b - 1));
}
}
int cc = 0;
for(int i = 1; i <= n - a + 1; i++)
for(int j = 1; j <= m - b + 1; j++)
s[++cc] = std::make_pair(i, j);
std::sort(s + 1, s + cc + 1, cmp);
int cnt = 0;
for(int u = 1; u <= cc; u++){
if(used[s[u].first][s[u].second])
continue;
cnt++;
ans1[cnt] = s[u].first;
ans2[cnt] = s[u].second;
ans3[cnt] = val[s[u].first][s[u].second];
for(int i = ans1[cnt] - a + 1; i <= ans1[cnt] + a - 1; i++)
for(int j = ans2[cnt] - b + 1; j <= ans2[cnt] + b - 1; j++)
if(i > 0 && j > 0 && !used[i][j] && i <= n - a + 1 && j <= m - b + 1)
used[i][j] = true;
}
printf("%d\n", cnt);
for(int i = 1; i <= cnt; i++)
printf("%d %d %I64d\n", ans1[i], ans2[i], ans3[i]);
}

 评论