记录编号	404103	评测结果	WWWWWWWWWWWWWWWWWWWW
题目名称	[国家集训队2012]矩阵乘法	最终得分	0
用户昵称	再见	是否通过	未通过
代码语言	C++	运行时间	13.376 s
提交时间	2017-05-12 20:31:02	内存使用	157.88 MiB

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int n,q,a[510][510],root[2000][510],cnt,sum[10000010],lc[10000010],rc[10000010],fa[10000010];
int b[30010],N,Q[510],idx,qroot[1010];

int erfen(int x){
	int l=1,r=N,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(b[mid]==x) return mid;
		if(b[mid]<x) l=mid+1;
		else r=mid-1;
	}
}

void add(int &o,int l,int r,int v,int T){
	if(!o) o=++cnt,sum[o]=sum[T];
	if(l==r){
		sum[o]++; return;
	}
	int mid=(l+r)>>1;
	if(v<=mid){
		if(fa[lc[o]]!=o) lc[o]=0;
		add(lc[o],l,mid,v,lc[T]);
		fa[lc[o]]=o;
	}
	else{
		if(fa[rc[o]]!=o) rc[o]=0;	
		add(rc[o],mid+1,r,v,rc[T]);
		fa[rc[o]]=o;
	}
	if(!lc[o]) lc[o]=lc[T];
	if(!rc[o]) rc[o]=rc[T];
	sum[o]=sum[lc[o]]+sum[rc[o]];
}

void build(int o,int l,int r){
	if(l==r){
		for(int i=1;i<=n;i++)
			add(root[o][i],1,N,a[l][i],root[o][i-1]);
		return;
	}
	int mid=(l+r)>>1;
	build(o<<1,l,mid); build(o<<1|1,mid+1,r);
	for(int i=1;i<=n;i++)
		for(int j=l;j<=r;j++)
			add(root[o][i],1,N,a[j][i],root[o][i-1]);
}

void gett(int o,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		Q[++idx]=o; return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) gett(o<<1,l,mid,ql,qr);
	if(mid<qr) gett(o<<1|1,mid+1,r,ql,qr);
}

int query(int x1,int y1,int x2,int y2,int k){
	idx=0; gett(1,1,n,x1,x2); int tot=0;
	for(int i=1;i<=idx;i++)
		qroot[++tot]=root[Q[i]][y1-1],qroot[++tot]=root[Q[i]][y2];
	int l=1,r=N,mid=0;
	while(l<=r){
		if(l==r) return l;
		mid=(l+r)>>1; int s=0;
		for(int i=1;i<=idx;i++)
			s+=sum[lc[qroot[2*i]]]-sum[lc[qroot[2*i-1]]];
		if(s<k){
			l=mid+1; k-=s;
			for(int i=1;i<=tot;i++) qroot[i]=rc[qroot[i]];
		}
		else{
			r=mid;
			for(int i=1;i<=tot;i++) qroot[i]=lc[qroot[i]];
		}
	}
}

int main(){
	freopen("nt2012_mat.in","r",stdin);
	freopen("nt2012_mat.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]),b[++N]=a[i][j];
	sort(b+1,b+N+1); N=unique(b+1,b+N+1)-b; N--;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=erfen(a[i][j]);
	build(1,1,n);
	while(q--){
		int x1,y1,x2,y2,k;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
		printf("%d\n",b[query(x1,y1,x2,y2,k)]);
	}
	return 0;
}