用的是权值线段树qaq

(i,j)位置维护的以(1,1)为左上角和以(i,j)为右下角的矩阵中的所有权值，每次加入(i,j)的权值，然后合并(i-1,j)和(i,j-1)的线段树，再减去(i-1,j-1)的线段树。 查询是就是(x2,y2)(x2,y1-1)(x1-1,y2)(x1-1,y1-1)做容斥。

目前样例都过不了，好像是合并的问题，但不知道哪里错了

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;

const int M=505;

int read(){
	int x=0,y=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') y=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*y;
}

int n,q,cnt=0,a[M][M],lsh[M*M],Num[M][M];
int num=0,rt[M*M],size[M*M*250],ch[M*M*250][2];
void pushup(int u){
	return (void)(size[u]=size[ch[u][0]]+size[ch[u][1]]);
}

void Insert(int &u,int l,int r,int x){
	if(!u) u=++num;size[u]=1;
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(x<=mid) Insert(ch[u][0],l,mid,x),ch[u][1]=0;
	else Insert(ch[u][1],mid+1,r,x),ch[u][0]=0;
	return (void)(pushup(u));
}

int Merge(int x,int y,int l,int r){
	if(!x||!y) return x+y;
	if(l==r){
		size[x]+=size[y];
		return x;
	}
	int mid=(l+r)>>1;
	ch[x][0]=Merge(ch[x][0],ch[y][0],l,mid);
	ch[x][1]=Merge(ch[x][1],ch[y][1],mid+1,r);
	pushup(x);
	return x;
}

int Del(int x,int y,int l,int r){
	if(!x||!y) return x+y;
	if(size[x]==size[y]){
		size[x]=0;
		ch[x][0]=ch[x][1]=0;
		return x;
	}
	if(l==r){
		size[x]-=size[y];
		return x;
	}
	int mid=(l+r)>>1;
	ch[x][0]=Del(ch[x][0],ch[y][0],l,mid);
	ch[x][1]=Del(ch[x][1],ch[y][1],mid+1,r);
	pushup(x);
	return x;
}

int Query(int A,int B,int C,int D,int l,int r,int k){
	if(l==r) return l;
	int mid=(l+r)>>1,p=size[ch[A][0]]-size[ch[B][0]]-size[ch[C][0]]+size[ch[D][0]];
	if(p>k) return Query(ch[A][0],ch[B][0],ch[C][0],ch[D][0],l,mid,k);
	else return Query(ch[A][1],ch[B][1],ch[C][1],ch[D][1],mid+1,r,k-p);
}

void Check(int u,int l,int r){
	printf("Check %d %d %d %d\n",u,l,r,size[u]);
	if(l==r) return ;
	int mid=(l+r)>>1;
	Check(ch[u][0],l,mid),Check(ch[u][1],mid+1,r);
}

void solve(){
	n=read(),q=read();cnt=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=read(),
			lsh[++cnt]=a[i][j],
			Num[i][j]=cnt;
	sort(lsh+1,lsh+cnt+1);int len=unique(lsh+1,lsh+cnt+1)-lsh-1;cnt=len;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=lower_bound(lsh+1,lsh+cnt+1,a[i][j])-lsh;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			printf("%d ",a[i][j]);
//		}
//		printf("\n");
//	}
//	for(int i=1;i<=cnt;i++) printf("%d ",lsh[i]);printf("\n");
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			Insert(rt[Num[i][j]],1,cnt,a[i][j]);
			if(Num[i-1][j]) rt[Num[i][j]]=Merge(rt[Num[i][j]],rt[Num[i-1][j]],1,cnt);
			if(Num[i][j-1]) rt[Num[i][j]]=Merge(rt[Num[i][j]],rt[Num[i][j-1]],1,cnt);
			if(Num[i-1][j-1]) rt[Num[i][j]]=Del(rt[Num[i][j]],rt[Num[i-1][j-1]],1,cnt);
//			printf("\nCheck %d %d:\n",i,j);
//			Check(Num[i][j],1,cnt);
		}
	}
	while(q--){
		int X1=read(),Y1=read(),X2=read(),Y2=read(),K=read();
		printf("%d\n",lsh[Query(rt[Num[X2][Y2]],rt[Num[X1-1][Y2]],rt[Num[X2][Y1-1]],rt[Num[X1-1][Y1-1]],1,cnt,K)]);
	}
}

int main(){
//	freopen("shuju.in","r",stdin);
	solve();
}