记录编号	367222	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]矩阵乘法	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	5.000 s
提交时间	2017-01-29 11:11:20	内存使用	10.36 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510,maxq=60010;
struct Q{int lx,ly,rx,ry,k,id;}q[maxq];
struct Q1{
	int x,l,r,d,id;
	bool operator<(const Q1 &q)const{return x<q.x;}
}q1[maxq<<1];
struct A{
	int x,y,d;
	bool operator<(const A &a)const{return d<a.d;}
}a[maxn*maxn],b[maxn*maxn];
void solve(int,int,int,int);
void add(int,int);
int query(int);
bool cmp(const A &a,const A &b){return a.x<b.x;}
int n,m,c[maxn]={0},ans[maxq],cnt,tmp[maxq]={0};
int main(){
	freopen("nt2012_mat.in","r",stdin);
	freopen("nt2012_mat.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		scanf("%d",&a[(i-1)*n+j].d);
		a[(i-1)*n+j].x=i;
		a[(i-1)*n+j].y=j;
	}
	sort(a+1,a+n*n+1);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d%d",&q[i].lx,&q[i].ly,&q[i].rx,&q[i].ry,&q[i].k);
		q[i].id=i;
	}
	solve(1,m,1,n*n);
	for(int i=1;i<=m;i++)printf("%d\n",a[ans[i]].d);
	return 0;
}
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[q[i].id]=L;
		return;
	}
	int M=(L+R)>>1;
	cnt=0;
	for(int i=l;i<=r;i++){
		q1[++cnt].x=q[i].lx-1;
		q1[cnt+1].x=q[i].rx;
		q1[cnt].l=q1[cnt+1].l=q[i].ly;
		q1[cnt].r=q1[cnt+1].r=q[i].ry;
		q1[cnt].d=-1;
		q1[cnt+1].d=1;
		q1[cnt].id=q1[cnt+1].id=i;
		cnt++;
	}
	sort(q1+1,q1+cnt+1);
	copy(a+L,a+M+1,b+L);
	sort(a+L,a+M+1,cmp);
	int i=L,j=1;
	while(i<=M&&j<=cnt){
		if(a[i].x<=q1[j].x)add(a[i++].y,1);
		else{
			tmp[q1[j].id]+=q1[j].d*(query(q1[j].r)-query(q1[j].l-1));
			j++;
		}
	}
	while(j<=cnt){
		tmp[q1[j].id]+=q1[j].d*(query(q1[j].r)-query(q1[j].l-1));
		j++;
	}
	while(i>L)add(a[--i].y,-1);
	copy(b+L,b+M+1,a+L);
	for(i=j=l;i<=r;i++){
		if(q[i].k<=tmp[i])swap(q[i],q[j++]);
		else q[i].k-=tmp[i];
		tmp[i]=0;
	}
	solve(l,j-1,L,M);
	solve(j,r,M+1,R);
}
inline void add(int x,int d){while(x<=n){c[x]+=d;x+=x&-x;}}
inline int query(int x){int ans=0;while(x){ans+=c[x];x&=x-1;}return ans;}
/*
整体二分，然后统计贡献就变成了有一堆点要求一堆矩形内的点数，
其实用不着二维树状数组，离线压掉一维之后直接上一维树状数组就行了。
这样还能去掉一个log，不知道你们为什么都要强行加上这个log。
*/