Test/yukicoder/yuki0755.test.cpp

View this file on GitHub
Last update: 2023-12-31 10:47:11+09:00
Problem: https://yukicoder.me/problems/no/755

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/755"

#include <bits/stdc++.h>
#include "DataStructure/CumulativeSum2D.hpp"
#include "DataStructure/CumulativeSum2D_imos.hpp"

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> A(m, vector<ll>(m));
    for(int y = 0; y < m; y++){
        for(int x = 0; x < m; x++){
            cin >> A[y][x];
        }
    }
    
    CumulativeSum2D<ll> CS(A);
    imos2D<int> imos(m, m);

    for(int ly = 0; ly < m; ly++){
        for(int ry = ly + 1; ry <= m; ry++){
            vector<pair<ll, int>> tmp(m + 1);
            for(int rx = 0; rx <= m; rx++){
                tmp[rx] = {CS.query(ly, 0, ry, rx), rx};
            }
            sort(tmp.begin(), tmp.end());
            for(int x = 0; x < m; ){
                int pre = x;
                while(x <= m && tmp[x].first == tmp[pre].first) x++;
                for(int l = pre; l < x; l++){
                    for(int r = l + 1; r < x; r++){
                        imos.add(ly, tmp[l].second, ry, tmp[r].second, 1);
                    }
                }
            }
        }
    }
    imos.build();
    while(n--){
        int y, x;
        cin >> y >> x;
        cout << imos[y - 1][x - 1] << '\n';
    }
}

#line 1 "Test/yukicoder/yuki0755.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/755"

#include <bits/stdc++.h>
#line 1 "DataStructure/CumulativeSum2D.hpp"
template <class T> struct CumulativeSum2D{
    int h, w;
    std::vector<std::vector<T>> dat;
    CumulativeSum2D(int H, int W) : h(H), w(W), dat(H + 1, std::vector<T>(W + 1, 0)) {}
    CumulativeSum2D(std::vector<std::vector<T>> &A) 
        : h(A.size()), w(A[0].size()), dat(h + 1, std::vector<T>(w + 1, 0)) {
        for(int y = 1; y <= h; y++){
            for(int x = 1; x <= w; x++){
                dat[y][x] = A[y - 1][x - 1] + dat[y][x - 1] + dat[y - 1][x] - dat[y - 1][x - 1];
            }
        }
    }
    void add(int y, int x, T z){
        assert(0 <= y && y < h);
        assert(0 <= x && x < w);
        dat[y + 1][x + 1] += z;
    }
    void build(){
        for(int y = 1; y <= h; y++) {
            for(int x = 1; x <= w; x++) {
                dat[y][x] += dat[y][x - 1] + dat[y - 1][x] - dat[y - 1][x - 1];
            }
        }
    }
    T query(int ly, int lx, int ry, int rx){
        assert(0 <= ly && ly <= ry && ry <= h);
        assert(0 <= lx && lx <= rx && rx <= w);
        return dat[ry][rx] - dat[ly][rx] - dat[ry][lx] + dat[ly][lx];
    }
};
#line 1 "DataStructure/CumulativeSum2D_imos.hpp"
template <class T> struct imos2D{
    int h, w;
    std::vector<std::vector<T>> dat;
    imos2D(int H, int W) : h(H), w(W), dat(H + 1, std::vector<T>(W + 1, 0)) {}
    void add(int ly, int lx, int ry, int rx, T v){
        assert(0 <= ly && ly <= ry && ry <= h);
        assert(0 <= lx && lx <= rx && rx <= w);
        dat[ry][rx] += v;
        dat[ly][rx] -= v;
        dat[ry][lx] -= v;
        dat[ly][lx] += v;
    }
    void build(){
        for(int i = 0; i <= h; i++) {
            for(int j = 1; j <= w; j++) {
                dat[i][j] += dat[i][j - 1];
            }
        }
        for(int i = 0; i <= w; i++) {
            for(int j = 1; j <= h; j++) {
                dat[j][i] += dat[j - 1][i];
            }
        }
    }
    const std::vector<T>& operator[](int y) const {
        assert(0 <= y && y < h);
        return dat[y];
    }
    std::vector<T>& operator[](int y) { 
        assert(0 <= y && y < h);
        return dat[y];
    }
};
#line 6 "Test/yukicoder/yuki0755.test.cpp"

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> A(m, vector<ll>(m));
    for(int y = 0; y < m; y++){
        for(int x = 0; x < m; x++){
            cin >> A[y][x];
        }
    }
    
    CumulativeSum2D<ll> CS(A);
    imos2D<int> imos(m, m);

    for(int ly = 0; ly < m; ly++){
        for(int ry = ly + 1; ry <= m; ry++){
            vector<pair<ll, int>> tmp(m + 1);
            for(int rx = 0; rx <= m; rx++){
                tmp[rx] = {CS.query(ly, 0, ry, rx), rx};
            }
            sort(tmp.begin(), tmp.end());
            for(int x = 0; x < m; ){
                int pre = x;
                while(x <= m && tmp[x].first == tmp[pre].first) x++;
                for(int l = pre; l < x; l++){
                    for(int r = l + 1; r < x; r++){
                        imos.add(ly, tmp[l].second, ry, tmp[r].second, 1);
                    }
                }
            }
        }
    }
    imos.build();
    while(n--){
        int y, x;
        cin >> y >> x;
        cout << imos[y - 1][x - 1] << '\n';
    }
}