记录编号	134138	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]矩阵乘法	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	12.149 s
提交时间	2014-10-29 15:34:10	内存使用	25.21 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEn=510,SIZEN=350010;
class TARRAY{
public:
	int n,m;
	int s[SIZEn][SIZEn];
	void clear(int a,int b){
		n=a,m=b;
		memset(s,0,sizeof(s));
	}
	#define lowbit(x) (x&-x)
	void change(int x,int y,int t){
		for(int i=x;i<=n;i+=lowbit(i))
			for(int j=y;j<=m;j+=lowbit(j))
				s[i][j]+=t;
	}
	int sum(int x,int y){
		int ans=0;
		for(int i=x;i;i-=lowbit(i))
			for(int j=y;j;j-=lowbit(j))
				ans+=s[i][j];
		return ans;
	}
	int query(int x,int y,int x1,int y1){
		return sum(x1,y1)-sum(x1,y-1)-sum(x-1,y1)+sum(x-1,y-1);
	}
}T;
class EVENT{
public:
	int id;
	int x,y,x1,y1,k;
};
EVENT S[SIZEN];
int N,Q;
int ans[SIZEN]={0};
int cnt[SIZEN]={0};
EVENT s1[SIZEN],s2[SIZEN];
void solve(int a,int b,int l,int r){//现确定a~b的答案都在[l,r]区间内
	if(a>b||l>r) return;
	if(l==r){
		for(int i=a;i<=b;i++) ans[S[i].id]=l;
		return;
	}
	//此时保证T中是清空的
	int mid=(l+r)/2;
	int p1=0,p2=0;
	for(int i=a;i<=b;i++){
		if(!S[i].id){//它是一个矩阵值
			if(S[i].k<=mid){
				T.change(S[i].x,S[i].y,1);
				s1[++p1]=S[i];
			}
			else s2[++p2]=S[i];
		}
		else{
			cnt[i]=T.query(S[i].x,S[i].y,S[i].x1,S[i].y1);
			if(cnt[i]>=S[i].k) s1[++p1]=S[i];
			else{
				S[i].k-=cnt[i];
				s2[++p2]=S[i];
			}
		}
	}
	for(int i=a;i<=b;i++) if(!S[i].id&&S[i].k<=mid) T.change(S[i].x,S[i].y,-1);
	for(int i=1;i<=p1;i++) S[a+i-1]=s1[i];
	for(int i=1;i<=p2;i++) S[a+p1+i-1]=s2[i];
	solve(a,a+p1-1,l,mid);
	solve(a+p1,a+p1+p2-1,mid+1,r);
}
void read(void){
	int n;
	scanf("%d%d",&n,&Q);
	T.clear(n,n);
	N=0;
	EVENT now;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			now.x=i,now.y=j,now.id=0;
			scanf("%d",&now.k);
			S[++N]=now;
		}
	}
	for(int i=1;i<=Q;i++){
		now.id=i;
		scanf("%d%d%d%d%d",&now.x,&now.y,&now.x1,&now.y1,&now.k);
		S[++N]=now;
	}
}
int main(){
	freopen("nt2012_mat.in","r",stdin);
	freopen("nt2012_mat.out","w",stdout);
	read();
	solve(1,N,0,1e9);
	for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
	return 0;
}