golB s'CBoriN

首先，不会主席树的同学请http://blog.csdn.net/metalseed/article/details/8045038 顺便再做做BZOJ3110

网传的整体二分算法本蒟蒻表示真看不懂，于是乱××了一个可怕的二维主席树，其中的一维是继承上一层处理的，另一维用树状数组，内存达到了可怕的O(N^2log^2N)，时间是O((N^2+Q)*log^2N)，都是贴着线过的，估计重新交一遍就TLE了吧

#include <cstdio>
#include <algorithm>
#define numnod 22030000
int root[501][501],ls[numnod],rs[numnod],cnt[numnod],a[501][501],A[250001],H=0,N,Q,n,ir[6666],dr[6666],Ni,Nd;
void add(int x,int y,int w)
{
	int lp=root[x][y],p=++n,l=1,r=H,new_root=p;
	cnt[p]=cnt[lp]+1;
	while (l<r)
	{
		int m=l+r>>1;
		if (w<=m)
			ls[p]=++n,rs[p]=rs[lp],p=ls[p],lp=ls[lp],r=m;
		else
			rs[p]=++n,ls[p]=ls[lp],p=rs[p],lp=rs[lp],l=m+1;
		cnt[p]=cnt[lp]+1;
	}
	root[x][y]=new_root;
}
void init()
{
	scanf("%d%d",&N,&Q);
	for (int i=1;i<=N;i++)
		for (int j=1;j<=N;j++)
			scanf("%d",&a[i][j]),A[++H]=a[i][j];
	std::sort(A+1,A+H+1);
	H=std::unique(A+1,A+H+1)-A-1;
	for (int i=1;i<=N;i++)
		for (int j=1;j<=N;j++)
			a[i][j]=std::lower_bound(A+1,A+H+1,a[i][j])-A;
	for (int j=1;j<=N;j++)
		for (int i=1;i<=N;i++)
		{
			root[i][j]=root[i-1][j];
			for (int k=(j&(j-1))+1;k<=j;k++)
				add(i,j,a[i][k]);
		}
}
int main()
{
	init();
	while (Q--)
	{
		int x1,y1,x2,y2,k,l=1,r=H;
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
		Ni=Nd=0;
		for (int i=y2;i;i&=i-1)
			ir[++Ni]=root[x2][i],dr[++Nd]=root[x1-1][i];
		for (int i=y1-1;i;i&=i-1)
			dr[++Nd]=root[x2][i],ir[++Ni]=root[x1-1][i];
		while (l<r)
		{
			int cL=0,m=l+r>>1;
			for (int i=Ni;i;i--)
				cL+=cnt[ls[ir[i]]];
			for (int i=Nd;i;i--)
				cL-=cnt[ls[dr[i]]];
			if (k<=cL)
			{
				for (int i=Ni;i;i--)
					ir[i]=ls[ir[i]];
				for (int i=Nd;i;i--)
					dr[i]=ls[dr[i]];
				r=m;
			}
			else
			{
				for (int i=Ni;i;i--)
					ir[i]=rs[ir[i]];
				for (int i=Nd;i;i--)
					dr[i]=rs[dr[i]];
				k-=cL,l=m+1;
			}
		}
		printf("%d\n",A[l]);
	}
	return 0;
}