CodeChef July Challenge 2016 Chef and Rectangle Array

問題

https://www.codechef.com/problems/CHSQARR
の行列が与えられる．個のクエリに対して以下の操作を行う．

• が与えられての範囲の数がすべて等しくなるように行列の要素の数字を増やすとき，増やす数の最小値を出力する

解法

範囲の和と範囲の最大値を使って，が最小になるようにすればいい．
範囲の和は累積和を使って求められる．
範囲の最大値はdequeを使って，最大となる数字がある位置を先頭にくるようにすれば，すべての範囲の最大値はで求められる．
一次元の場合を考えると

2

5

4

7

1

3

という数列があって範囲の大きさが3となる範囲の最大値を求めたい．
まず初めの3つを見ているときのdequeの中身は{1,2}となる（順に5のindex，4のindex）．

2

5

4

7

1

3

次の3つを見ているときのdequeの中身は{3}となる（7のindex）．

2

5

4

7

1

3

このようにdequeの値を持つとしゃくとり法の要領で最大値を保持しながら範囲をずらすことができる．
今回はこれを二次元の場合に落としこめばいい．

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e9
#define MOD (int)(1e9+7)

typedef long long ll;

int A[1000][1000];
int sum[1000][1000];

int value(pair<int,int> p) {
    return A[p.first][p.second];
}

int main(void) {
    int i, j, N, M, Q;
    scanf("%d%d",&N,&M);
    rep (i,N) rep (j,M) scanf("%d",A[i]+j);
    rep (i,N) {
        sum[i][0] = A[i][0];
        REP (j,1,M) sum[i][j] = sum[i][j-1] + A[i][j];
    }
    rep (j,M) rep (i,N-1) sum[i+1][j] += sum[i][j];

    scanf("%d",&Q);
    while (Q--) {
        int a, b;
        scanf("%d%d",&a,&b);
        int ans = INF;
        deque<int> cm[1000];
        for (j = 0; j < M; j++) {
            for (i = 0; i < a; i++) {
                while (!cm[j].empty() && A[i][j] >= A[cm[j].back()][j])
                    cm[j].pop_back();
                cm[j].push_back(i);
            }
        }
        for (; i <= N; i++) {
            deque<pair<int,int>> sq;
            for (j = 0; j < b; j++) {
                while (!sq.empty() && A[cm[j].front()][j] >= value(sq.back()))
                    sq.pop_back();
                sq.push_back(make_pair(cm[j].front(),j));
            }
            for (; j <= M; j++) {
                int mx = value(sq.front());
                int s = sum[i-1][j-1];
                if (i > a)
                    s -= sum[i-a-1][j-1];
                if (j > b)
                    s -= sum[i-1][j-b-1];
                if (i > a && j > b)
                    s += sum[i-a-1][j-b-1];
                ans = min(ans,mx*a*b-s);

                if (j == M) break;
                if (sq.front().second == j-b)
                    sq.pop_front();
                while (!sq.empty() && A[cm[j].front()][j] >= value(sq.back()))
                    sq.pop_back();
                sq.push_back(make_pair(cm[j].front(),j));
            }
            if (i == N) break;
            for (j = 0; j < M; j++) {
                if (cm[j].front() == i-a)
                    cm[j].pop_front();
                while (!cm[j].empty() && A[i][j] >= A[cm[j].back()][j])
                    cm[j].pop_back();
                cm[j].push_back(i);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}