题目传送门(BZOJ)
>原文链接<

题解 :

$N$特别小, 数点的话直接开一个二维树状数组即可.

我们可以把矩阵读入之后, 按权值排序, 这样就可以二分了.

对于一个询问$(x1, y1, x2, y2, k)$, 二分出一个$mid$, 把$1\sim mid$这部分点都加进去, 权值为$1$

查询子矩形中权值和是否大于$k$, 若大于等于就向左走, 否则向右走.

解决了单组询问, 对于多组询问考虑整体二分.

$solve(L, R, l, r)$表示解决$[L, R]$这部分询问, 答案下标区间在$[l, r]$

验证上有一点不同, 若一次验证是小于$k$的, 我们把这部分减掉, 这样下次再验证这个询问时, 只需要加从$mid+1$开始的点, 具体实现的确是可以这样的,

因为某个询问往左走, 那么我们都不会减掉这次验证的答案,

若它往右走, 那么下次验证一定是从$mid+1$开始的

对于$l = r$, 把$[L, R]$这部分的答案都置成$a[l].val$即可

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 510;#define P(i, j) ((i-1)*n+j)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}struct POINT { int x, y, v; inline bool operator < (const POINT &A) const { return v < A.v; }}a[N*N];struct QUERY { int x1, x2, y1, y2, k, id;}q[61000], b[61000];int n, Q, t[N][N], ans[61000];inline void add(int x, int y, int c) { for(int i = x; i <= n; i += i&-i) for(int j = y; j <= n; j += j&-j) t[i][j] += c;}inline int inq(int x, int y) { int re = 0; for(int i = x; i; i -= i&-i) for(int j = y; j; j -= j&-j) re += t[i][j]; return re;}void solve(int L, int R, int l, int r) { if(L > R) return ; if(l == r) { for(int i = L; i <= R; i ++ ) ans[q[i].id] = a[l].v; return ; } int mid = (l+r) >> 1; int pl = L, pr = R; for(int i = l; i <= mid; i ++ ) add(a[i].x, a[i].y, 1); for(int i = L; i <= R; i ++ ) { int sum = inq(q[i].x2, q[i].y2)- inq(q[i].x1-1, q[i].y2)- inq(q[i].x2, q[i].y1-1)+ inq(q[i].x1-1, q[i].y1-1); if(sum >= q[i].k) b[pl++] = q[i]; else q[i].k -= sum, b[pr--] = q[i]; } for(int i = L; i <= R; i ++ ) q[i] = b[i]; for(int i = l; i <= mid; i ++ ) add(a[i].x, a[i].y, -1); solve(L, pr, l, mid), solve(pl, R, mid+1, r);}int main() { n = rd(), Q = rd(); for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) { a[P(i, j)].v = rd(); a[P(i, j)].x = i; a[P(i, j)].y = j; } sort(a+1, a+n*n+1); for(int i = 1; i <= Q; i ++ ) { q[i].x1 = rd(), q[i].y1 = rd(), q[i].x2 = rd(), q[i].y2 = rd(); q[i].k = rd(), q[i].id = i; } solve(1, Q, 1, n*n); for(int i = 1; i <= Q; i ++ ) printf("%d\n", ans[i]);}