记录编号	153989	评测结果	WWWWWWWWWEEEEEEEEEEE
题目名称	[国家集训队2012]矩阵乘法	最终得分	0
用户昵称	new ioer	是否通过	未通过
代码语言	C++	运行时间	3.677 s
提交时间	2015-03-20 19:32:13	内存使用	12.05 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define lb(x) x&-x
using namespace std;
const int N = 511;
const int M = 121000;
int mat[N][N],c[N][N];
struct Ask{
	int id,x1,y1,x2,y2,x;
}Q[M],Q1[M],Q2[M];
int n,m,tot,tim,nn,a0[N*N],Ans[M];

void Add(int x,int y,int d){
	for(int i=x;i<=n;i+=lb(i))
		for(int j=y;j<=n;j+=lb(j))
			c[i][j]+=d;
	return;
}

int Sum(int x,int y){
	int res=0;
	for(int i=x;i;i-=lb(i)){
		for(int j=y;j;j-=lb(j)){
			res+=c[i][j];
		}
	}
	return res;
}

void Solve(int h,int t,int l,int r){
	if(l==r){
		for(int i=h;i<=t;i++)
			if(Q[i].id>0) Ans[Q[i].id]=a0[l];
		return;
	}
	int mid=(l+r)>>1,i1=0,i2=0,ran;
	for(int i=h;i<=t;i++){
		if(Q[i].id==0){
			if(Q[i].x<mid) Add(Q[i].x1,Q[i].y1,1),Q1[++i1]=Q[i];
			else Q2[++i2]=Q[i]; 
		}
		else{
			ran=Sum(Q[i].x2,Q[i].y2)-Sum(Q[i].x2,Q[i].y1-1)-Sum(Q[i].x1-1,Q[i].y2)+Sum(Q[i].x1-1,Q[i].y1-1);
			if(ran>=Q[i].x) Q1[++i1]=Q[i];
			else Q[i].x-=ran,Q2[++i2]=Q[i];
		}
	}
	for(int i=1;i<=i1;i++)
		if(Q1[i].id==0) Add(Q1[i].x1,Q1[i].y1,-1);
	memcpy(Q+h,Q1+1,sizeof(Ask)*i1);
	memcpy(Q+h+i1,Q2+1,sizeof(Ask)*i2);
	Solve(h,h+i1-1,l,mid);Solve(h+i1,t,mid+1,r);
	return;
}

void Readin(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&mat[i][j]),a0[++a0[0]]=mat[i][j];
	sort(a0+1,a0+a0[0]+1);
	nn=1;
	for(int i=2;i<=a0[0];i++) if(a0[i]!=a0[i-1]) a0[++nn]=a0[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			mat[i][j]=lower_bound(a0+1,a0+nn+1,mat[i][j])-a0;
			Q[++tot]=(Ask){0,i,j,0,0,mat[i][j]};
		}
	for(int x1,x2,y1,y2,k,i=1;i<=m;i++){
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
		Q[++tot]=(Ask){++tim,x1,y1,x2,y2,k-1};
	}
	return;
}

int main(){
	#define Read
	#ifdef Read
		freopen("nt2012_mat.in","r",stdin);
		freopen("nt2012_mat.out","w",stdout);
	#endif
	Readin();
	Solve(1,tot,1,nn);
	for(int i=1;i<=tim;i++)
		printf("%d\n",Ans[i]);
	return 0;
}