Description
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
Input
第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
Output
对于每组询问输出第K小的数。
Sample Input
2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3
Sample Output
1
3
HINT
矩阵中数字是10^9以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。
我们可以整体二分，这样可以转换成对于每个矩形计算其内部有多少点。
扫描线+树状数组就可以了，时间复杂度O(Nlog^2N)。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=<<;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
const int maxc=;
struct Array {
int x,y,val;
bool operator < (const Array& ths) const {return val<ths.val;}
}A[maxn];
struct Query {
int x,y,l,r,k,id;
}q[maxm];
int n,m,r,Q[maxm],tmp[maxm],ans[maxm];
struct Point {
int x,y;
bool operator < (const Point& ths) const {return x<ths.x;}
}P[maxn];
int res[maxm];
struct Rect {
int x,l,r,tp,id;
bool operator < (const Rect& ths) const {return x<ths.x;}
}B[maxm<<];
int sumv[maxc],cur[maxc],clo;
int query(int x) {
int res=;
for(;x;x-=x&-x) if(cur[x]==clo) res+=sumv[x];
return res;
}
void add(int x,int v) {
for(;x<=r;x+=x&-x)
if(cur[x]==clo) sumv[x]+=v;
else cur[x]=clo,sumv[x]=v;
}
void solve(int l,int r,int h,int t) {
if(h>t) return;
if(l==r) {
rep(i,h,t) ans[q[Q[i]].id]=A[l].val;
return;
}
int mid=l+r>>,m1=,m2=;
rep(i,l,mid) P[++m1]=(Point){A[i].x,A[i].y};
rep(i,h,t) {
res[i]=;
B[++m2]=(Rect){q[Q[i]].x-,q[Q[i]].l,q[Q[i]].r,-,i};
B[++m2]=(Rect){q[Q[i]].y,q[Q[i]].l,q[Q[i]].r,,i};
}
sort(P+,P+m1+);sort(B+,B+m2+);int j=;clo++;
rep(i,,m2) {
while(j<=m1&&P[j].x<=B[i].x) add(P[j].y,),j++;
res[B[i].id]+=B[i].tp*(query(B[i].r)-query(B[i].l-));
}
int L=h,R=t;
rep(i,h,t) if(res[i]>=q[Q[i]].k) tmp[L++]=Q[i];
else q[Q[i]].k-=res[i],tmp[R--]=Q[i];
rep(i,h,t) Q[i]=tmp[i];//开始手残没有写这行话QAQ(AQ)*
solve(l,mid,h,R);solve(mid+,r,R+,t);
}
int main() {
r=read();m=read();
rep(i,,r) rep(j,,r) A[++n]=(Array){i,j,read()};
sort(A+,A+n+);
rep(i,,m) q[Q[i]=q[i].id=i].x=read(),q[i].l=read(),q[i].y=read(),q[i].r=read(),q[i].k=read();
solve(,n,,m);
rep(i,,m) printf("%d\n",ans[i]);
return ;
}