主页
归档
朋友
关于

题解 CF15D Map

setset 瞎搞

首先非常显然，一个矩形(x1,y1,x2,y2)(x1, y1, x2, y2)的代价就是∑i=x1x2∑j=y1y2h[i][j]−min⁡x1≤i≤x2,y1≤j≤y2h[i][j]\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]f[i][j]表示以(i,j)(i, j)为左上角的矩形的代价。即矩形(i,j,i+a−1,j+b−1)(i, j, i + a - 1, j + b - 1)的代价。

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

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

我们对每行都建一个stst表，考虑我们把当前我们要求的区间里的h[i][j]h[i][j]都丢进一个setset中。

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

发现其实对于每一行，只有它的在范围内的最小值才有贡献，所setset中只需要放每行的最小值（可以用stst表快速查询）。

我们再考虑如下图所示。

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

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

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

复杂度O(nmlog⁡n)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]);
}

QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动，使用 Azurus 作为主题。