卡常大合集:见代码

#include<iostream>
#include<math.h>
#include<algorithm>
unsigned n,q,bl,a[500][500],rk[250000],l1,r1,l2,r2,num;
unsigned t[250000],c[500],ans[60000],ch[500],kb[250000];
unsigned lb,rb,mid;
unsigned char chh,bit[10],k;
struct mo{
	unsigned x1,y1,x2,y2,k,id;
}m[60000];
inline bool cmp(mo m1,mo m2){
	if(ch[m1.x1]!=ch[m2.x1])return ch[m1.x1]<ch[m2.x1];
	if(ch[m1.y1]!=ch[m2.y1]){
		if(ch[m1.x1]&1)return m1.y1<m2.y1;
		else return m1.y1>m2.y1;
	}if(ch[m1.x2]!=ch[m2.x2]){
		if(ch[m1.y1]&1)return m1.x2<m2.x2;
		else return m1.x2>m2.x2;
	}if(ch[m1.y1]&1)return m1.y2<m2.y2;
	return m1.y2>m2.y2;
}inline unsigned fin(){
	num=0,chh=getchar_unlocked();
	for(;chh<'0'||chh>'9';)chh=getchar_unlocked();
	for(;chh<'9'+1&&chh>'0'-1;)num=(num<<3)+(num<<1)+chh-'0',chh=getchar_unlocked();
	return num;
}void fout(unsigned x){
	k=0;
	for(;x!=0;)bit[k]=x%10,k++,x/=10;
	for(register int i(k-1);i>-1;--i)putchar_unlocked(bit[i]+'0');
	return;
}int main(){
	n=fin(),q=fin(),bl=n/pow(q,0.25)/3+1;
	for(register unsigned i(0);i<n;++i){
		ch[i]=i/bl;
		for(register unsigned j(0);j<n;++j)a[i][j]=fin(),rk[i*n+j]=a[i][j],kb[i*n+j]=i;
	}std::sort(rk,rk+n*n);
	for(register unsigned i(0);i<n;++i){
		for(unsigned j(0);j<n;++j){
			lb=0,rb=n*n;
			while(lb<rb){
				mid=(lb+rb)>>1;
				if(rk[mid]>=a[i][j])rb=mid;
				else lb=mid+1;
			}a[i][j]=lb;
		}
	}for(register unsigned i(0);i<q;++i){
		m[i].id=i;
		m[i].x1=fin(),m[i].y1=fin(),m[i].x2=fin(),m[i].y2=fin(),m[i].k=fin();
		--m[i].x1,--m[i].y1,--m[i].x2,--m[i].y2;
	}std::sort(m,m+q,cmp),l1=1,r1=0,l2=1,r2=0;
	for(register unsigned i(0);i<q;++i){
		for(;l1<m[i].x1;){
			for(register unsigned j(l2);j<r2+1;++j)--t[a[l1][j]],--c[kb[a[l1][j]]];
			++l1;
		}for(;l1>m[i].x1;){
			--l1;
			for(register unsigned j(l2);j<r2+1;++j)++t[a[l1][j]],++c[kb[a[l1][j]]];
		}for(;r1<m[i].x2;){
			++r1;
			for(register unsigned j(l2);j<r2+1;++j)++t[a[r1][j]],++c[kb[a[r1][j]]];
		}for(;r1>m[i].x2;){
			for(register unsigned j(l2);j<r2+1;++j)--t[a[r1][j]],--c[kb[a[r1][j]]];
			--r1;
		}for(;l2<m[i].y1;){
			for(register unsigned j=(l1);j<r1+1;++j)--t[a[j][l2]],--c[kb[a[j][l2]]];
			++l2;
		}for(;l2>m[i].y1;){
			--l2;
			for(register unsigned j=(l1);j<r1+1;++j)++t[a[j][l2]],++c[kb[a[j][l2]]];
		}for(;r2<m[i].y2;){
			++r2;
			for(register unsigned j=(l1);j<r1+1;++j)++t[a[j][r2]],++c[kb[a[j][r2]]];
		}for(;r2>m[i].y2;){
			for(register unsigned j=(l1);j<r1+1;++j)--t[a[j][r2]],--c[kb[a[j][r2]]];
			--r2;
		}for(register unsigned j(0);j<n;++j){
			if(m[i].k<c[j]+1){
				for(register unsigned l(j*n);l<(j+1)*n;++l){
					if(m[i].k<t[l]+1){
						ans[m[i].id]=l;
						goto cal;
					}else m[i].k-=t[l];
				}
			}else m[i].k-=c[j];
		}cal:continue;
	}for(register unsigned i(0);i<q;++i)fout(rk[ans[i]]),putchar('\n');
	return 0;
}