整体二分 WA0pts 求调

#include<bits/stdc++.h>
using namespace std;

const int N = 505,Q = 60005;

int n,q;
int arr[N][N];

struct Node {
	int l,r;
	int sum;
}tre[4*N];

#define mid (tre[now].l+tre[now].r>>1)
#define lson (now*2)
#define rson (now*2+1)

void build(int now,int l,int r) {
	tre[now].l=l,tre[now].r=r;
	if(l==r) return;
	build(lson,l,mid);build(rson,mid+1,r);
}

int query(int now,int l,int r) {
	if(tre[now].l>r || tre[now].r<l) return 0;
	if(tre[now].l>=l && tre[now].r<=r) return tre[now].sum;
	return query(lson,l,mid) + query(rson,mid+1,r);
}

void change(int now,int p,int k) {
	if(tre[now].l>p || tre[now].r<p) return;
	tre[now].sum+=k;
	if(tre[now].l==tre[now].r) return;
	change(lson,p,k);change(rson,p,k);
}

#undef mid

struct Qst {
	int x,y,id;
};

int a[N*N],m;
void init() {
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[i*n-n+j] = arr[i][j];
	sort(a+1,a+1+n*n);
	m = unique(a+1,a+1+n*n) - a - 1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			arr[i][j] = lower_bound(a+1,a+1+m,arr[i][j]) - a;
}

int ans[Q],delta[Q],cnt[Q];

void solve(int l,int r,vector<Qst>& vec) {
	if(l==r) {
		for(auto& [x,y,id]:vec)
			ans[abs(id)] = l;
		return;
	}
	int mid = l+r>>1;
	
	vector<Qst> lvec,rvec;
	sort(vec.begin(),vec.end(),[](Qst a,Qst b) {
		return a.x == b.x ? b.id : a.x<b.x;
	});
	
	for(auto& [x,y,id]:vec) {
		if(id) {
			delta[abs(id)] += query(1,0,y) * (id<0 ? -1:1);
		}else if(arr[x][y]<=mid) {
			change(1,y,1);
			lvec.push_back({x,y,id});
		}else {
			rvec.push_back({x,y,id});
		}
	}
	
	for(auto& [x,y,id]:vec) {
		if(id) {
			if(cnt[abs(id)] - delta[abs(id)] > 0) {
				rvec.push_back({x,y,id});
			}else {
				lvec.push_back({x,y,id});
			}
		}else if(arr[x][y]<=mid) {
			change(1,y,-1);
		}
	}
	
	for(auto& [x,y,id]:vec) {
		if(cnt[abs(id)] - delta[abs(id)] > 0) cnt[abs(id)] -= delta[abs(id)];
		delta[abs(id)] = 0;
	}
	
	vec.clear();
	vec.shrink_to_fit();
	
	solve(l,mid,lvec);
	solve(mid+1,r,rvec);
}

int main() {
	cin >> n >> q;
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			cin >> arr[i][j];
	
	init(); 
	
	int x1,y1,x2,y2;
	
	vector<Qst> vec;
	for(int i=1;i<=q;++i) {
		cin >> x1 >> y1 >> x2 >> y2 >> cnt[i];
		vec.push_back({x2,y2,i});
		if(x1-1>=0 && y1-1>=0) vec.push_back({x1-1,y1-1,i});
		if(y1-1>=0) vec.push_back({x2,y1-1,-i});
		if(x1-1>=0) vec.push_back({x1-1,y2,-i});
	}
	
	build(1,0,n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			vec.push_back({i,j,0});
	
	solve(1,m,vec);
	
	for(int i=1;i<=q;++i) cout << a[ans[i]] << '\n';
	
	return 0;
}