全局二分的经典题。
最初试图用持久化线段树和分块，然后欢快地tle+mle了。看到jason_yu和mhy过了，只能说自己的常数优化还不过关啊。
第一次写这种二分。就是把所有东西扔进来快速排序，顺便考虑每个询问应该被扔到哪边。然后加树状数组来统计就好了。
代码巨丑。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
struct query {
int x1, y1, x2, y2, k, n;
};
int _d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
const int maxn = 509;
const int maxq = 310009;
int n, m, t, maxa, a[maxn][maxn], b[maxn][maxn], ttm;
int d[maxn * maxn], ans[maxq], tdr[maxq];
query q[maxq];
void btChg(int x, int y, int v) {
for (int p = x; p <= n; p += (p & -p))
for (int q = y; q <= n; q += (q & -q))
if (b[p][q] ^ ttm) {
a[p][q] = v;
b[p][q] = ttm;
}
else
a[p][q] += v;
}
int btQry(int x, int y) {
int s = 0;
for (int p = x; p; p -= (p & -p))
for (int q = y; q; q -= (q & -q))
if (b[p][q] == ttm)
s += a[p][q];
return s;
}
void qSort(int vl, int vr, int ql, int qr) {
if (vl == vr) {
for (int i = ql; i <= qr; ++ i)
if (q[i]. n > -1)
ans[q[i]. n] = d[vl];
}
else {
++ ttm;
int vm = (vl + vr) >> 1;
for (int i = ql; i <= qr; ++ i)
if (q[i]. n == -1) {
if (q[i]. k <= d[vm]) {
btChg(q[i]. x1, q[i]. y1, 1);
tdr[i] = 0;
}
else
tdr[i] = 1;
}
for (int i = ql; i <= qr; ++ i)
if (q[i]. n > -1) {
int g = btQry(q[i]. x2, q[i]. y2) + btQry(q[i]. x1, q[i]. y1)
- btQry(q[i]. x1, q[i]. y2) - btQry(q[i]. x2, q[i]. y1);
if (g < q[i]. k) {
q[i]. k -= g;
tdr[i] = 1;
}
else
tdr[i] = 0;
}
int i = ql, j = qr;
while (i < j) {
for (; i < j && tdr[i] == 0; ++ i);
for (; i < j && tdr[j] == 1; -- j);
if (i <= j) {
swap(q[i], q[j]);
swap(tdr[i], tdr[j]);
++ i;
-- j;
}
}
for (i = ql - 1; i < qr && tdr[i + 1] == 0; ++ i);
if (ql <= i)
qSort(vl, vm, ql, i);
if (i + 1 <= qr)
qSort(vm + 1, vr, i + 1, qr);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
ttm = 0;
readInt(n);
readInt(m);
t = 0;
maxa = 0;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j) {
readInt(q[t]. k);
if (q[t]. k > maxa)
maxa = q[t]. k;
d[i * n + j - n - 1] = q[t]. k;
q[t]. x1 = i;
q[t]. y1 = j;
q[t]. n = -1;
++ t;
}
sort(d, d + n * n);
for (int i = 0; i < m; ++ i) {
readInt(q[t]. x1);
-- q[t]. x1;
readInt(q[t]. y1);
-- q[t]. y1;
readInt(q[t]. x2);
readInt(q[t]. y2);
readInt(q[t]. k);
q[t]. n = i;
++ t;
}
qSort(0, n * n - 1, 0, t - 1);
for (int i = 0; i < m; ++ i)
printf("%d\n", ans[i]);
}