Yet Another Median Task

#include <bits/stdc++.h>
using namespace std;
const int MAX = 810;

int b[MAX][MAX];

void add(int x, int y, int val) {
    for (int i = x; i < MAX; i += (i & -i)) {
        for (int j = y; j < MAX; j += (j & -j)) {
            b[i][j] += val;
        }
    }
}

int sum(int x, int y) {
    int ret = 0;
    for (int i = x; i > 0; i -= (i & -i)) {
        for (int j = y; j > 0; j -= (j & -j)) {
            ret += b[i][j];
        }
    }
    return ret;
}

int query(int x1, int y1, int x2, int y2) {
    return sum(x2, y2)-sum(x1-1, y2)-sum(x2, y1-1)+sum(x1-1, y1-1);
}

int getSize(int x1, int y1, int x2, int y2) {
    return (x2-x1+1)*(y2-y1+1);
}

int n, q, ans[1010];
int gr[MAX][MAX];
vector<pair<int, pair<int, int>>> order;
vector<pair<int, pair<pair<int, int>, pair<int, int>>>> queries;

void solve(int l, int r, vector<int> &v) {
    if (l == r) {
        for (int x : v) {
            ans[x] = order[l].first;
        }
        return;
    }
    int mid = (l+r)/2;
    for (int k = l; k <= mid; ++k) {
        auto [i, j] = order[k].second;
        add(i, j, 1);
    }
    vector<int> left, right;
    for (int x : v) {
        auto [x1, y1] = queries[x].second.first;
        auto [x2, y2] = queries[x].second.second;
        int ss = query(x1, y1, x2, y2);
        int sz = getSize(x1, y1, x2, y2);
        if (ss >= sz-ss) {
            left.push_back(x);
        } else {
            right.push_back(x);
        }
    }
    solve(mid+1, r, right);
    for (int k = l; k <= mid; ++k) {
        auto [i, j] = order[k].second;
        add(i, j, -1);
    }
    solve(l, mid, left);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> gr[i][j];
            order.push_back({gr[i][j], {i, j}});
        }
    }
    sort(order.begin(), order.end());
    for (int i = 0, x1, y1, x2, y2; i < q; ++i) {
        cin >> x1 >> y1 >> x2 >> y2;
        queries.push_back({i, {{x1, y1}, {x2, y2}}});
    }
    vector<int> v(q);
    iota(v.begin(), v.end(), 0);
    solve(0, n*n-1, v);
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}