题意：
给你一个N*N的矩阵，没有修改，每次询问一个子矩形中的第K小数。
题目链接
思路：
当它只有一列时，其实就是区间第K大，也就是整体二分可以解决的。
现在到了二维，只需要将之前的树状数组改成二维的就可以了。
注意事项：
二维的容斥稍显繁杂，注意一下
二维树状数组不要打错
code：
#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int Q=60005;
struct node{int pt1_x,pt1_y,pt2_x,pt2_y,k,id,tp;}a[N*N+Q],a1[N*N+Q],a2[N*N+Q];
int n,q,cnt,ans[Q];
inline int read()
{
int s=0,w=1; char ch=getchar();
for(;'0'>ch||ch>'9';ch=getchar())if(ch=='-')w=-1;
for(;'0'<=ch&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
return s*w;
}
struct tree{
int c[N][N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y,int v)
{
int yy=y;
for(;x<=n;x+=lowbit(x))
for(y=yy;y<=n;y+=lowbit(y))
c[x][y]+=v;
}
inline int query(int x,int y)
{
int yy=y,anss=0;
for(;x;x-=lowbit(x))
for(y=yy;y;y-=lowbit(y))
anss+=c[x][y];
return anss;
}
}T;
void solve(int L,int R,int l,int r)
{
if(l>r) return;
if(L==R)
{
for(int i=l;i<=r;++i)
if(a[i].tp) ans[a[i].id]=L;
return;
}
int mid=L+R>>1,cnt1=0,cnt2=0;
for(int i=l;i<=r;++i)
{
if(!a[i].tp)
{
if(a[i].k<=mid) T.add(a[i].pt1_x,a[i].pt1_y,1),a1[++cnt1]=a[i];
else a2[++cnt2]=a[i];
}
else
{
int num=T.query(a[i].pt2_x,a[i].pt2_y)-T.query(a[i].pt2_x,a[i].pt1_y-1)-T.query(a[i].pt1_x-1,a[i].pt2_y)+T.query(a[i].pt1_x-1,a[i].pt1_y-1);
if(a[i].k<=num) a1[++cnt1]=a[i];
else a2[++cnt2]=a[i],a2[cnt2].k-=num;
}
}
for(int i=l;i<=r;++i)
if(!a[i].tp&&a[i].k<=mid) T.add(a[i].pt1_x,a[i].pt1_y,-1);
for(int i=l;i<=l+cnt1-1;++i)a[i]=a1[i-l+1];
for(int i=l+cnt1;i<=r;++i)a[i]=a2[i-l-cnt1+1];
solve(L,mid,l,l+cnt1-1);
solve(mid+1,R,l+cnt1,r);
}
int main()
{
n=read(),q=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[++cnt]=node{i,j,0,0,read(),0,0};
for(int i=1;i<=q;++i)
{
int _x1=read(),_y1=read(),_x2=read(),_y2=read(),_k=read();
a[++cnt]=node{_x1,_y1,_x2,_y2,_k,i,1};
}
solve(0,1e9,1,cnt);
for(int i=1;i<=q;++i)
printf("%d\n",ans[i]);
return 0;
}