P2216

二维树状数组最值裸题 wa了#5, 6 求助

#include<bits/stdc++.h>

using i64 = long long;
constexpr int P = 998244353;

struct Fenwick {
    int n, m;
    std::vector<std::vector<int>> a, b;
    Fenwick (int _n, int _m) : n(_n), m(_m) {
        a.resize(n + 1, std::vector<int>(m + 1, -1000000000));
        b.resize(n + 1, std::vector<int>(m + 1, 1000000000));
    }
    void add(int p1, int p2, int v){
        for(int i = p1; i <= n; i += (i & -i)) {
            for(int j = p2; j <= m; j += (j & -j)) {
                a[i][j] = std::max(a[i][j], v);
                b[i][j] = std::min(b[i][j], v);
            }
        }
    }
    int rangeask(int row1, int row2, int col1, int col2, std::vector<std::vector<int>> & in) {
        int Max = -1000000000, Min = 1000000000;
        int c1 = col1, c2 = col2;
        while(row1 <= row2){
            while(row2 - (row2 & -row2) >= row1){
                col1 = c1, col2 = c2;
                while(col1 <= col2){
                    while(col2 - (col2 & -col2) >= col1){
                        Max = std::max(Max, a[row2][col2]);
                        Min = std::min(Min, b[row2][col2]);
                        col2 -= (col2 & -col2);
                    }
                    Max = std::max(Max, in[row2][col2]);
                    Min = std::min(Min, in[row2][col2]);
                    col2--;
                }
                row2 -= (row2 & -row2);
            }
            for(int i = c1; i <= c2; ++i){
                Max = std::max(Max, in[row2][i]);
                Min = std::min(Min, in[row2][i]);
            }
            row2--;
        }
        //std::cout << Min << ' ' << Max << '\n';
        return Max - Min;
    }
};

void solve(){
    int a, b, n;
    std::cin >> a >> b >> n;
    std::vector<std::vector<int>> in(a + 1, std::vector<int>(b + 1));
    for(int i = 1; i <= a; ++i){
        for(int j = 1; j <= b; ++j){
            std::cin >> in[i][j];
        }
    }
    Fenwick f(a, b);
    int res = 2000000000;
    // [i + 1 - n, i]
    // [j + 1 - n, j]
    for(int i = 1; i <= a; ++i){
        for(int j = 1; j <= b; ++j){
            f.add(i, j, in[i][j]);
            if(i >= n && j >= n){
                //std::cout << i + 1 - n << ' ' << i << ' ' << j + 1 - n << ' ' << j << " --> ";
                res = std::min(res, f.rangeask(i + 1 - n, i, j + 1 - n, j, in));
            }
        }
    }
    std::cout << res;
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;  // std::cin >> t;
    while(t--){
        solve();
    }

    return 0;
}