首页 > itarticle > 题解 cf15d map

题解 cf15d map

admin 11月 14, 2020 0

$set$ 瞎搞

首先非常显然，一个矩形$(x1, y1, x2, y2)$的代价就是$displaystylesum_{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
 


#define ll long long
#define INF 2147483647

int (){
    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("%dn", cnt);
    for(int i = 1; i <= cnt; i++)
        printf("%d %d %I64dn", ans1[i], ans2[i], ans3[i]);
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能