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

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=510,M=6e5+10;
int n,q,a[N][N],ans[M];
struct opt{
	int x1,x2,y1,y2,k,id,tp;
}Q[M];
struct bit{
	int a[N];
	void add(int p,int d){
		for (;p<=n;p+=p&-p) a[p]+=d;
	}
	int sum(int r){
		int ans=0;
		for (;r;r-=r&-r) ans+=a[r];
		return ans;
	}
};
struct RMQ{
	bit a[N];
	void add(int x,int y,int d){
		for (;x<=n;x+=x&-x) a[x].add(y,d);
	}
	int sum(int x,int y){
		int ans=0;
		for (;x;x-=x&-x) ans+=a[x].sum(y);
		return ans;
	}
	int sum(int x1,int y1,int x2,int y2){
		return sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
	}
}T;
bool cmp(const opt &x,const opt &y){
	return x.tp==y.tp?x.id<y.id:x.tp<y.tp;
}
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 mid=(l+r)>>1,nl=0;
	for (int i=L;i<=R;i++)
	if (!Q[i].id){
		if (Q[i].k<=mid){
			T.add(Q[i].x1,Q[i].y1,1);
			Q[i].tp=0;
			++nl;
		}
		else Q[i].tp=1;
	}
	else{
		int sum=T.sum(Q[i].x1,Q[i].y1,Q[i].x2,Q[i].y2);
		if (Q[i].k>sum){
			Q[i].k-=sum;
			Q[i].tp=1;
		}
		else Q[i].tp=0,++nl;
	}
	for (int i=L;i<=R;i++)
	if (!Q[i].id&&Q[i].k<=mid)
		T.add(Q[i].x1,Q[i].y1,-1);
	sort(Q+L,Q+R+1,cmp);
	solve(L,L+nl-1,l,mid);
	solve(L+nl,R,mid+1,r);
}
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]);
		int pos=(i-1)*n+j;
		Q[pos].x1=i;Q[pos].y1=j;Q[pos].k=a[i][j];
	}
	for (int i=n*n+1;i<=n*n+q;i++){
		scanf("%d%d%d%d%d",&Q[i].x1,&Q[i].y1,&Q[i].x2,&Q[i].y2,&Q[i].k);
		Q[i].id=i-n*n;
	}
	solve(1,n*n+q,1,1e9);
	for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}