这题就是整体二分的板儿，只不过变成二维的。
那么就用二维树状数组好啦。
至于二维树状数组，看了代码就懂了。
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define rg registertypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxn = 505;const int maxq = 6e4 + 5;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}int n, q, cnt = 0;struct Node{ int xa, ya, xb, yb, k, id;}t[maxn * maxn + maxq], tl[maxn * maxn + maxq], tr[maxn * maxn + maxq];int ans[maxq];ll c[maxn][maxn];inline ll lowbit(const int& x) {return x & -x;}inline void update(const int& px, const int& py, const int& d){ for(int x = px; x <= n; x += lowbit(x)) for(int y = py; y <= n; y += lowbit(y)) c[x][y] += d; }inline ll query(const int& px, const int& py){ ll ret = 0; for(int x = px; x; x -= lowbit(x)) for(int y = py; y; y -= lowbit(y)) ret += c[x][y]; return ret;}inline ll Query(const int& xa, const int& ya, const int& xb, const int& yb){ return query(xb, yb) - query(xb, ya - 1) - query(xa - 1, yb) + query(xa - 1, ya - 1); }inline void solve(const int& vl, const int& vr, const int& ql, const int& qr){ if(ql > qr) return; if(vl == vr) { for(int i = ql; i <= qr; ++i) if(t[i].id) ans[t[i].id] = vl; return; } int mid = (vl + vr) >> 1, id1 = 0, id2 = 0; for(int i = ql; i <= qr; ++i) { if(!t[i].id) { if(t[i].k <= mid) update(t[i].xa, t[i].ya, 1), tl[++id1] = t[i]; else tr[++id2] = t[i]; } else { ll sum = Query(t[i].xa, t[i].ya, t[i].xb, t[i].yb); if(sum >= t[i].k) tl[++id1] = t[i]; else t[i].k -= sum, tr[++id2] = t[i]; } } for(int i = 1; i <= id1; ++i) if(!tl[i].id && tl[i].k <= mid) update(tl[i].xa, tl[i].ya, -1); for(int i = 1; i <= id1; ++i) t[ql + i - 1] = tl[i]; for(int i = 1; i <= id2; ++i) t[ql + id1 + i - 1] = tr[i]; solve(vl, mid, ql, ql + id1 - 1); solve(mid + 1, vr, ql + id1, qr);}int main(){ n = read(); q = read(); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) { t[++cnt].k = read(); t[cnt].xa = i; t[cnt].ya = j; t[cnt].id = 0; } for(int i = 1; i <= q; ++i) t[++cnt].xa = read(), t[cnt].ya = read(), t[cnt].xb = read(), t[cnt].yb = read(), t[cnt].k = read(), t[cnt].id = i; solve(0, 1e9, 1, cnt); for(int i = 1; i <= q; ++i) write(ans[i]), enter; return 0;}