可以用二维树状数组套值域线段树来做，复杂度：O( (n*n+q) * logn logn log10^9 )
但作为作为整体二分的例题，还是用整体二分来写了一下。对整体二分有一点感觉了。
整体二分，顾名思义，二分答案，只不过不是对单独一个询问，而是对所有询问，具体过程可以想象成对询问的不断分类（根据其答案区间不断往下分）。比如最开始所有询问的答案区间是[amin,amax]，我们现在分出两个区间[amin,amid],和[amid+1,amax]，然后将当前区间[amin,amax]的所有询问根据某些信息，分配到两个区间，使得其答案的可能的区间范围就是它所属的区间，当区间长度为1时，该区间包含的询问的答案就是该区间的那个数。
形象一点，可以把二分比作赶鸭子（询问）回窝（答案），单独对一个询问二分是只赶一只鸭子，向左区间或右区间赶，直到回窝，而整体二分就是赶一群鸭子，前者只需单刀直入，找到答案，而后者还需要回朔。
整体二分的优势是可以在分配询问时共享一些东西，从而避免掉每次单独算的低效，从而优化复杂度。
#include <cstdio>
#include <vector>
#include <algorithm>
#define oo 0x3f3f3f3f
#define N 510
#define M 60010
using namespace std; struct Pair {
int v;
int x, y;
Pair(){}
Pair( int v, int x, int y ):v(v),x(x),y(y){}
bool operator<( const Pair &o ) const {
return v<o.v;
}
};
bool operator<( const Pair &a, int b ) {
return a.v<b;
}
bool operator<( int a, const Pair &b ) {
return a<b.v;
}
struct Query {
int id;
int xmin, xmax;
int ymin, ymax;
int k;
Query( int id, int x0, int x1, int y0, int y1, int k ):
id(id),xmin(x0),xmax(x1),ymin(y0),ymax(y1),k(k){}
}; int n, m;
int ww[N][N], vmin, vmax;
int bit[N][N];
int ans[M];
Pair prs[N*N]; int ptot;
vector<Query> vq;
int q[N*N]; void modify( int x, int y, int v ) {
for( register int i=x; i<=n; i+=i&-i )
for( register int j=y; j<=n; j+=j&-j )
bit[i][j] += v;
}
int query( int x, int y ) {
int rt = ;
for( register int i=x; i; i-=i&-i )
for( register int j=y; j; j-=j&-j )
rt += bit[i][j];
return rt;
}
int query( int xmin, int xmax, int ymin, int ymax ) {
return query(xmax,ymax)-query(xmin-,ymax)-query(xmax,ymin-)+query(xmin-,ymin-);
}
void binary( int lf, int rg, vector<Query> vq ) {
if( vq.empty() ) return;
if( lf==rg ) {
for( int t=; t<vq.size(); t++ )
ans[vq[t].id] = lf;
return;
}
int mid=lf+((rg-lf)>>);
int lpos = lower_bound( prs+, prs++ptot, lf ) - prs;
int rpos = upper_bound( prs+, prs++ptot, mid ) - prs - ;
for( int i=lpos; i<=rpos; i++ )
modify( prs[i].x, prs[i].y, + );
vector<Query> ql, qr;
for( int t=; t<vq.size(); t++ ) {
int c = query( vq[t].xmin, vq[t].xmax, vq[t].ymin, vq[t].ymax );
if( vq[t].k<=c )
ql.push_back( vq[t] );
else {
qr.push_back( vq[t] );
qr.back().k -= c;
}
}
for( int i=lpos; i<=rpos; i++ )
modify( prs[i].x, prs[i].y, - );
binary( lf, mid, ql );
binary( mid+, rg, qr );
}
int main() {
scanf( "%d%d", &n, &m );
vmin=oo, vmax=-oo;
for( int i=; i<=n; i++ )
for( int j=; j<=n; j++ ) {
scanf( "%d", &ww[i][j] );
vmin = min( vmin, ww[i][j] );
vmax = max( vmax, ww[i][j] );
prs[++ptot] = Pair( ww[i][j], i, j );
}
sort( prs+, prs++ptot );
for( int i=,x0,x1,y0,y1,k; i<=m; i++ ) {
scanf( "%d%d%d%d%d", &x0, &y0, &x1, &y1, &k );
vq.push_back( Query( i, x0, x1, y0, y1, k ) );
}
binary( vmin, vmax, vq );
for( int i=; i<=m; i++ )
printf( "%d\n", ans[i] );
}