CF15D-Map题解

发表于 分类于

题目传送门

题意：有一个 n×mn\times m 的矩阵，每个格子有一个权值。每次操作会选择一个 x×yx\times y 的矩形区域，花费为“每个位置的权值减去最小权值”之和，区域之间不能重叠。每次会选择花费最小的区间，如果有重复，则优先选上面的，再优先选左边的。输出每次的区域和花费。

显然选区域不会影响其他区域的花费，只会影响其他区域是否可选。思考可以发现，选择一个左上角为 (a,b)(a,b) 的区域，会导致左上角在 (a−x+1∼a+x−1,b−y+1∼b+y−1)(a-x+1\sim a+x-1,b-y+1\sim b+y-1) 的所有区域不可选。于是每次操作找到当前能选的最优区域，更改其他区域即可。

具体实现上，要用横竖两遍滑动窗口求出每个区域的最小值，再用二维前缀和求出每个区域的权值和，则该区域的花费为权值和减去 x×yx\times y 倍最小值。

统计答案时，由于常数要求比较严格，需要预先对所有区域进行从优到劣的排序，每次看一个区域是否可选，如果可选就更新，否则到下一个。

对于判断是否可选，可以使用二维树状数组维护，也可以暴力更新。对于暴力更新的复杂度证明：首先发现选的区域个数不会超过 n⋅mx⋅y\frac{n\cdot m}{x\cdot y}，而每次暴力更新的复杂度为 4xy4xy，所以更新的总复杂度为 4nm4nm。

暴力更新 By cxm1024

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) f=(ch=='-'?-1:f),ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int a[1010][1010],s[1010][1010],t[1010][1010],sum[1010][1010];
bool vis[1010][1010];
signed main() {
    int n=read(),m=read(),x=read(),y=read();
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            a[i][j]=read();
            sum[i][j]=sum[i][j-1]+a[i][j];
        }
        deque<pair<int,int> > q;
        for(int j=0;j<y;j++) {
            while(!q.empty()&&q.back().second>=a[i][j])
                q.pop_back();
            q.push_back({j,a[i][j]});
        }
        for(int j=y;j<=m;j++) {
            if(!q.empty()&&q.front().first==j-y)
                q.pop_front();
            while(!q.empty()&&q.back().second>=a[i][j])
                q.pop_back();
            q.push_back({j,a[i][j]});
            s[i][j-y+1]=q.front().second;
        }
    }
    for(int j=1;j<=m-y+1;j++) {
        deque<pair<int,int> > q;
        for(int i=0;i<x;i++) {
            while(!q.empty()&&q.back().second>=s[i][j])
                q.pop_back();
            q.push_back({i,s[i][j]});
        }
        for(int i=x;i<=n;i++) {
            if(!q.empty()&&q.front().first==i-x)
                q.pop_front();
            while(!q.empty()&&q.back().second>=s[i][j])
                q.pop_back();
            q.push_back({i,s[i][j]});
            t[i-x+1][j]=q.front().second;
        }
    }
    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++)
            sum[i][j]+=sum[i-1][j];
    vector<pair<int,pair<int,int> > > v;
    for(int i=1;i<=n-x+1;i++)
        for(int j=1;j<=m-y+1;j++) {
            int res=sum[i+x-1][j+y-1];
            res-=sum[i+x-1][j-1]+sum[i-1][j+y-1];
            res+=sum[i-1][j-1];
            v.push_back({res-t[i][j]*x*y,{i,j}});
        }
    sort(v.begin(),v.end());
    vector<pair<int,pair<int,int> > > ans;
    for(auto [tmp,pos]:v) {
        auto [i,j]=pos;
        if(vis[i][j]) continue;
        ans.push_back({tmp,pos});
        for(int di=-x+1;di<=x-1;di++)
            for(int dj=-y+1;dj<=y-1;dj++)
                if(i+di>0&&j+dj>0) vis[i+di][j+dj]=1;
    }
    printf("%lu\n",ans.size());
    for(auto [tmp,pos]:ans)
        printf("%lld %lld %lld\n",pos.first,pos.second,tmp);
    return 0;
}

二维树状数组 By vepifanov

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
int n;
int m;
int f[1001][1001];
int ww[1001][1001], w[1001][1001], g[1001][1001];
long long s[1001][1001];
ii st[1001];

vector<pair<long long, pair<int, int> > > all;
vector<pair<pair<int, int>, long long > > res;

int add (int x, int y) {
    for (int p = x; p <= n; p |= (p + 1))
        for (int q = y; q <= m; q |= (q + 1))
            f[p][q]++;
}

int get (int x, int y) {
    int s = 0;
    for (int p = x; p > 0; p = (p & (p + 1)) - 1)
        for (int q = y; q > 0; q = (q & (q + 1)) - 1)
            s += f[p][q];
    return s;
}

int main() {
    int a, b;
    scanf ("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf ("%d", &g[i][j]);
    memset (s, 0, sizeof (s));
    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
            s[i][j] = s[i + 1][j] + s[i][j + 1] - s[i + 1][j + 1] + g[i][j];
    for (int i = 0; i < n; i++) {
        int r = 0, l = 0;
        for (int j = 0; j < m; j++) {
            while (l < r && st[l].second + b <= j) l++;
            while (r > l && st[r - 1].first > g[i][j]) r--;
            st[r++] = make_pair (g[i][j], j);
            if (j - b + 1 >= 0) ww[i][j - b + 1] = st[l].first;
        }
    }

    for (int j = 0; j + b <= m; j++) {
        int r = 0, l = 0;
        for (int i = 0; i < n; i++) {
            while (l < r && st[l].second + a <= i) l++;
            while (r > l && st[r - 1].first > ww[i][j]) r--;
            st[r++] = make_pair (ww[i][j], i);
            if (i - a + 1 >= 0) w[i - a + 1][j] = st[l].first;
        }
    }

    for (int i = 0; i + a <= n; i++)
        for (int j = 0; j + b <= m; j++) {
            long long cur = s[i][j] - s[i + a][j] - s[i][j + b] + s[i + a][j + b];
            cur -= (long long)w[i][j] * a * b;
            all.push_back (make_pair (cur, make_pair (i, j)));
        }
    sort (all.begin (), all.end ());
    for (int i = 0; i < all.size (); i++) {
        long long q = all[i].first;
        int x = all[i].second.first;
        int y = all[i].second.second;
        if (get (x + a, y + b) - get (max (x - a + 1, 0), y + b) - get (x + a, max (y - b + 1, 0)) + get (max (x - a + 1, 0), max (y - b + 1, 0)) == 0) {
            res.push_back (make_pair (make_pair (x, y), q));
            add (x + 1, y + 1);
        }
    }
    printf ("%d\n", res.size ());
    for (int i = 0; i < res.size (); i++)
        printf ("%d %d %I64d\n", res[i].first.first + 1, res[i].first.second + 1, res[i].second);
    return 0;
}