xxx250 @ 2020-11-11 08:00:07
#include<bits/stdc++.h>
using namespace std;
const int N=555,M=6e4+5;
struct ooo{int a,b,c,d,id,k;}t[M],t1[M];
struct kkk{int x,y,v;}p[N*N];
bool operator<(const kkk a,const kkk b){return a.v<b.v;}
int n,q,cnt,c[N][N],ans[N];
void add(int x,int y,int k){
for(int i=x;i<=n;i+=i&-i)
for(int j=y;j<=n;j+=j&-j)
c[i][j]+=k;
}
int get(int x,int y){
int res=0;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
res+=c[i][j];
return res;
}
void xxx(int l,int r,int x,int y){
if(x>y)return;
if(l==r){
for(int i=x;i<=y;i++)
ans[t[i].id]=p[l].v;return;
}
int mid=l+r>>1,lt=x,rt=y;
for(int i=l;i<=mid;i++)add(p[i].x,p[i].y,1);
for(int i=x;i<=y;i++){
int k=get(t[i].c,t[i].d)-get(t[i].a-1,t[i].d)-get(t[i].c,t[i].b-1)+get(t[i].a-1,t[i].b-1);
if(t[i].k<=k)t1[lt++]=t[i];
else t1[rt]=t[i],t1[rt--].k-=k;
}
for(int i=l;i<=mid;i++)add(p[i].x,p[i].y,-1);
for(int i=x;i<=y;i++)t[i]=t1[i];
xxx(l,mid,x,lt-1);xxx(mid+1,r,lt,y);
}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&p[++cnt].v);
p[cnt].x=i;p[cnt].y=j;
}
for(int i=1;i<=q;i++)
scanf("%d%d%d%d%d",&t[i].a,&t[i].b,&t[i].c,&t[i].d,&t[i].k),t[i].id=i;
sort(p+1,p+1+cnt);xxx(1,cnt,1,q);
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
}
```cpp