其实这题跟矩阵乘法没有任何卵关系，直接整体二分，用二维树状数组维护（刚刚学会>_<），复杂度好像有点爆炸（好像有十几亿不知道是不是算错了），但我们不能怂啊23333。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,qq;
int map[][];
int p[];
int ans[];
struct node
{
int x1,x2,y1,y2,k;
}op[];
struct nd
{
int x,y,w;
friend bool operator < (nd aa,nd bb)
{
return aa.w<bb.w;
}
}la[*];int tot;
int c[][];
void add(int x,int y,int z)
{
for(int i=x;i<=n;i+=(i&(-i)))
{
for(int j=y;j<=n;j+=(j&(-j)))
{
c[i][j]+=z;
}
}
}
int qur(int x,int y)
{
int ans=;
for(int i=x;i;i-=(i&(-i)))
{
for(int j=y;j;j-=(j&(-j)))
{
ans+=c[i][j];
}
}
return ans;
}
int tmp[][];
void solve(int L,int R,int l,int r)
{
if(L>R)return ;
if(l==r)
{
for(int i=L;i<=R;i++)ans[p[i]]=la[l].w;
return ;
}
int mid=(l+r)>>;
for(int i=l;i<=mid;i++)add(la[i].x,la[i].y,);
int cnt1=,cnt2=;
for(int i=L;i<=R;i++)
{
int y=qur(op[p[i]].x2,op[p[i]].y2)-qur(op[p[i]].x1-,op[p[i]].y2)-qur(op[p[i]].x2,op[p[i]].y1-)+qur(op[p[i]].x1-,op[p[i]].y1-);
if(y>=op[p[i]].k)tmp[][++cnt1]=p[i];
else op[p[i]].k-=y,tmp[][++cnt2]=p[i];
}
for(int i=l;i<=mid;i++)add(la[i].x,la[i].y,-);
int l1=L+cnt1-;
for(int i=;i<=cnt1;i++)p[L+i-]=tmp[][i];
for(int i=;i<=cnt2;i++)p[l1+i]=tmp[][i];
solve(L,l1,l,mid);solve(l1+,R,mid+,r);
}
int main()
{
scanf("%d%d",&n,&qq);
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
scanf("%d",&map[i][j]);
la[++tot].x=i;la[tot].y=j;la[tot].w=map[i][j];
}
}
sort(la+,la+tot+);
for(int i=;i<=qq;i++)
{
scanf("%d%d%d%d%d",&op[i].x1,&op[i].y1,&op[i].x2,&op[i].y2,&op[i].k);
p[i]=i;
}
solve(,qq,,n*n);
for(int i=;i<=qq;i++)
{
printf("%d\n",ans[i]);
}
return ;
}