整体二分求卡常

#include<bits/stdc++.h>
using namespace std;
class BIT2D
{
	private:
		int n,m;
		int tree[505][505];
		int lowbit(int x)
		{
			return x&-x;
		}
	public:
		BIT2D(int _n,int _m)
		{
			//tree.resize(_n,vector<int>(_m));
			n=_n,m=_m;
		}
		void add(int x,int y,int k)
		{
			for(int i=x;i<=n;i+=lowbit(i))
			{
				for(int j=y;j<=m;j+=lowbit(j))
				{
					tree[i][j]+=k;
				}
			}
		}
		int query(int x,int y)
		{
			int ans=0;
			for(int i=x;i>=1;i-=lowbit(i))
			{
				for(int j=y;j>=1;j-=lowbit(j))
				{
					ans+=tree[i][j];
				}
			}
			return ans;
		}
};
struct idc
{
	int x,y,k;
	bool friend operator<(idc a,idc b)
	{
		return a.k<b.k;
	}
};
struct query
{
	int a,b,c,d,k;
};

int n,q,cnt=0;
idc arr[250010];
query Q[60005];
int ans[60005];
BIT2D t(505,505);
void getans(int a[],int sz,int l,int r)
{
	if(sz<=0) return;
	if(l==r)
	{
		for(int i=1;i<=sz;i++)
		{
			ans[a[i]]=arr[l].k;
		}
		return;
	}
	int lsz=0,rsz=0;
	int larr[60005]={0};
	int rarr[60005]={0};
	int mid=(l+r)>>1;
	for(int i=l;i<=mid;i++) 
	{
		t.add(arr[i].x,arr[i].y,1);
	}
	for(int j=1;j<=sz;j++)
	{
		int i=a[j];
		int sum=t.query(Q[i].c,Q[i].d)-t.query(Q[i].c,Q[i].b-1)-t\
		.query(Q[i].a-1,Q[i].d)+t.query(Q[i].a-1,Q[i].b-1);
		if(sum>=Q[i].k)
		{
			larr[++lsz]=i;
		}
		else
		{
			rarr[++rsz]=i;
			Q[i].k-=sum;
		}
	}
	for(int i=l;i<=mid;i++) 
	{
		t.add(arr[i].x,arr[i].y,-1);
	}
	getans(larr,lsz,l,mid);
	getans(rarr,rsz,mid+1,r);
}
inline void read(int& x)
{
	x=0;
	char ch=getchar_unlocked();
	bool flag=false;
	while(ch<'0' || ch>'9')
	{
		if(ch=='-') flag=1;
		ch=getchar_unlocked();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar_unlocked();
	}
	if(flag) x=-x;
}
inline void write(int x)
{
	if(x<0)
	{
		putchar_unlocked('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar_unlocked(x%10+'0');
}
signed main()
{
	read(n);read(q);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			read(arr[++cnt].k);
			arr[cnt].x=i;
			arr[cnt].y=j;
		}
	}
	for(int i=1;i<=q;i++)
	{
		read(Q[i].a);
        read(Q[i].b);
        read(Q[i].c);
        read(Q[i].d);
        read(Q[i].k);
	}
	sort(arr+1,arr+1+cnt);
	int a[60005]={0};
	for(int i=1;i<=q;i++)
	{
		a[i]=i;
	}
	getans(a,q,1,cnt);
	for(int i=1;i<=q;i++)
	{
		write(ans[i]);
        putchar('\n');
	}
	return 0;
}