整体二分求调，悬2关

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
struct yyy
{
    ll k,x1,x2,y1,y2,bh,f;
}yd[1000005],b[1000005],c[1000005];
struct xian{
    ll y1,y2,x,sy,f;
}yx[1000005];
ll n,q,d,ans[1000005],z[1000005],tr[505];
bool cmp(yyy a,yyy b){
    return a.f==b.f?a.x1<b.x1:a.f<b.f;
}
bool cmp1(xian a,xian b){
    return a.x<b.x;
}
void gd(ll x,ll z){
    // cout<<x<<endl;
    while(x<=n){
        tr[x]+=z;
        x+=x&(-x);

    }
}
ll cd(ll x){
    ll s=0;
    while(x){
        s+=tr[x];
        x^=x&(-x);
    }
    return s;
}
void ef(ll l,ll r,ll zl,ll zr){
    if(l>r)return;
    // cout<<l<<' '<<r<<' '<<zl<<' '<<zr<<":::"<<endl;
    if(zl==zr){
        for(ll i=l;i<=r;i++)
            if(yd[i].f==1)
                ans[yd[i].bh]=zl;
        return;
    }

    ll mid=(zl+zr)>>1,xd=0,d1=0,d2=0;
    sort(yd+l,yd+r+1,cmp);

    for(ll i=l;i<=r;i++){
        if(yd[i].f==1){
            z[i]=0;
            yx[++xd]={yd[i].y1-1,yd[i].y2,yd[i].x1-1,i,-1};
            yx[++xd]={yd[i].y1-1,yd[i].y2,yd[i].x2,i,1};
        }
    }
    sort(yx+1,yx+1+xd,cmp1);
    for(ll i=1,j=l;i<=xd;i++){
        while(j<=r&&yd[j].x1<=yx[i].x&&yd[j].f==0){
            if(yd[j].k<=mid)b[++d1]=yd[j],gd(yd[j].y1,1);
            else c[++d2]=yd[j];
            // cout<<yd[j].x1<<' '<<yd[j].y1<<' '<<j<<' '<<r<<endl;
            j++;
        }
        // for(ll i=1;i<=5;i++)cout<<cd(i)<<' ';
        // cout<<endl;
        z[yx[i].sy]+=(cd(yx[i].y2)-cd(yx[i].y1))*yx[i].f;
        // cout<<mid<<' '<<yx[i].sy<<' '<<yx[i].y1<<' '<<yx[i].y2<<' '<<yx[i].f<<' '<<yx[i].x<<endl;
        // cout<<cd(yx[i].y2)-cd(yx[i].y1)<<endl;
    }
    // cout<<1<<endl;
    for(ll i=l;i<=r;i++){
        if(yd[i].f==1){
            // cout<<yd[i].x1<<' '<<yd[i].x2<<' '<<yd[i].y1<<' '<<yd[i].y2<<' '<<z[i]<<endl;
            if(z[i]>=yd[i].k){
                b[++d1]=yd[i];
            }
            else yd[i].k-=z[i],c[++d2]=yd[i];
        }
    }

    for(ll i=1;i<=d1;i++)
        yd[i+l-1]=b[i];
    for(ll i=1;i<=d2;i++)
        yd[i+l+d1-1]=c[i];
    for(ll i=1;i<=d1;i++)
        if(b[i].f==0)
            gd(b[i].y1,-1);

    ef(l,l+d1-1,zl,mid),ef(l+d1,r,mid+1,zr);
}
int main(){
    ll aa,bb,cc,dd,ee;
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            scanf("%lld",&aa);
            yd[++d]={aa,i,0,j,0,d,0};
        }
    }
    for(ll i=1;i<=q;i++){
        scanf("%lld%lld%lld%lld%lld",&aa,&bb,&cc,&dd,&ee);
        yd[++d]={ee,aa,cc,bb,dd,i,1};
    }
    ef(1,d,0,1e9);
    for(ll i=1;i<=q;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}