C++(clang++ 11.0.1) 解法, 执行用时: 614ms, 内存消耗: 24012K, 提交时间: 2022-09-01 10:45:35

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e2+5,M=6e4+5,inf=2147483647;
struct opt{
	int ax,ay,bx,by,k,posx,posy,id,ty;
}q[N*N+M],q1[N*N+M],q2[N*N+M];
int n,m,x,y,k,cnt,tree[N][N],ans[M],maxn=-0x3f3f3f3f,minn=0x3f3f3f3f;
int lowbit(int x){return x&(-x);}
void add(int x,int y,int v){
	for(int i=x;i<=n;i+=lowbit(i))for(int j=y;j<=n;j+=lowbit(j))tree[i][j]+=v;
}
int query(int x,int y){
	int ret=0;
	for(int i=x;i;i-=lowbit(i))for(int j=y;j;j-=lowbit(j))ret+=tree[i][j];
	return ret;
}
void solve(int l,int r,int L,int R){
	if(l>r||L>R)return ;
	if(l==r){
		for(int i=L;i<=R;i++)if(q[i].ty)ans[q[i].id]=l;
		return ;
	}
	int mid=(l+r)>>1,cnt1=0,cnt2=0;
	for(int i=L;i<=R;i++){
		if(q[i].ty){
			int tmp=query(q[i].bx,q[i].by)-query(q[i].ax-1,q[i].by)-query(q[i].bx,q[i].ay-1)+query(q[i].ax-1,q[i].ay-1);
			if(tmp>=q[i].k)q1[++cnt1]=q[i];
			else q[i].k-=tmp,q2[++cnt2]=q[i];
		}else{
			if(q[i].ax<=mid)q1[++cnt1]=q[i],add(q[i].posx,q[i].posy,1);
			else q2[++cnt2]=q[i];
		}
	}
	for(int i=1;i<=cnt1;i++)if(!q1[i].ty)add(q1[i].posx,q1[i].posy,-1);
	for(int i=1;i<=cnt1;i++)q[L+i-1]=q1[i];
	for(int i=1;i<=cnt2;i++)q[L+cnt1+i-1]=q2[i];
	solve(l,mid,L,L+cnt1-1);
	solve(mid+1,r,L+cnt1,R);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&x),q[++cnt]=(opt){x,-1,-1,-1,-1,i,j,-1,0},minn=min(minn,x),maxn=max(maxn,x);
	for(int i=1;i<=m;i++){
		int ax,ay,bx,by;
		scanf("%d %d %d %d %d",&ax,&ay,&bx,&by,&k);
		q[++cnt]=(opt){ax,ay,bx,by,k,-1,-1,i,1};
	}
	solve(minn,maxn,1,cnt);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}