本文共 1724 字，大约阅读时间需要 5 分钟。

整体二分  然后在二维树状数组上更新

#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<set>#include<cmath>#include<algorithm>using namespace std;char c;inline void read(int &a){	a=0;do c=getchar();while(c<'0'||c>'9');	while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();}int n,m,cnt,T;int t[705][705],ans[60005];int id[70005],tmp[60005];bool mark[60005];struct que{	int x1,x2,y1,y2,K;}q[60005];struct data{int x,y,val;inline friend bool operator <( data a,data b){return a.val<b.val;}}a[250005];void add(int x,int y,int val){	for(int i=x;i<=n;i+=i&-i)		for(int j=y;j<=n;j+=j&-j)			t[i][j]+=val;}int query(int x,int y){	int tmp=0;	for(int i=x;i;i-=i&-i)		for(int j=y;j;j-=j&-j)			tmp+=t[i][j];	return tmp;}int query(int k){	int x1=q[k].x1,y1=q[k].y1,x2=q[k].x2,y2=q[k].y2;return query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1);}void solve(int l,int r,int L,int R){	if(l>r)return;	if(L==R)return;	int mid=(L+R)>>1;	while(a[T+1].val<=mid&&T<cnt){add(a[T+1].x,a[T+1].y,1);T++;	}	while(a[T].val>mid){add(a[T].x,a[T].y,-1),T--;	}    int cnt=0;    for(int i=l;i<=r;i++)	{		if(query(id[i])>q[id[i]].K-1)		{			mark[i]=1;ans[id[i]]=mid;cnt++;		}		else mark[i]=0;	}	int l1=l,l2=l+cnt;	for(int i=l;i<=r;i++)		if(mark[i])tmp[l1++]=id[i];		else tmp[l2++]=id[i];	for(int i=l;i<=r;i++)id[i]=tmp[i];	solve(l,l1-1,L,mid);solve(l1,l2-1,mid+1,R);}int main(){      read(n);read(m);	int mx=0;	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			a[++cnt].x=i,a[cnt].y=j,read(a[cnt].val),		mx=max(a[cnt].val,mx);	sort(a+1,a+cnt+1);	for(int i=1;i<=m;i++)		read(q[i].x1),read(q[i].y1),read(q[i].x2),read(q[i].y2),read(q[i].K);	for(int i=1;i<=m;i++)id[i]=i;	solve(1,m,0,mx+1);	for(int i=1;i<=m;i++)		printf("%d\n",ans[i]);	return 0;}