给你一个 的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第 小数。
考虑 的数据。
不难想到暴力二分，遍历矩阵，计算 的数的个数。
设 为值域上界，总体时间复杂度为 。
考虑 的数据。
发现与普通区间 kth 的区别在于这题的 是二维的。
同样，我们可以将 存成一维数组形式，利用二维树状数组来整体二分。
设 表示询问 的答案在 中（此处 指一维数组）。函数内部，我们将 的数染黑，利用二维树状数组结合 计算询问区间内黑点个数，递归处理左右区间。
由于二维树状数组单次修改查询是 的，所以时间复杂度为 。
#include<bits/stdc++.h>
using namespace std;
const int N=507,M=6e4+7;
int tr[N][N],id[M],n;
int lowbit(int x){
return x&-x;
}
void add(int x,int y,int c){
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)){
tr[i][j]+=c;
}
}
}
int query(int x,int y){
int res=0;
for(int i=x;i>0;i-=lowbit(i)){
for(int j=y;j>0;j-=lowbit(j)){
res+=tr[i][j];
}
}
return res;
}
struct node{
int x,y,v;
bool operator<(node a)const{
return v<a.v;
}
}mat[N*N];
struct Q{
int x_1,y_1,x_2,y_2,k;
}q[M];
int cas,cur[M],q1[M],q2[M],ans[M];
int get(int x,int y){
return (x-1)*n+y;
}
void Solve(int l,int r,int ql,int qr){
if(ql>qr)return;
if(l==r){
for(int i=ql;i<=qr;i++)ans[id[i]]=mat[l].v;
return;
}
int mid=(l+r)>>1;
int cnt1=0,cnt2=0;
for(int i=l;i<=mid;i++)add(mat[i].x,mat[i].y,1);
for(int i=ql;i<=qr;i++){
int sum=query(q[id[i]].x_2,q[id[i]].y_2)-query(q[id[i]].x_1-1,q[id[i]].y_2)-
query(q[id[i]].x_2,q[id[i]].y_1-1)+query(q[id[i]].x_1-1,q[id[i]].y_1-1);
int num=cur[id[i]]+sum;
if(num>=q[id[i]].k)q1[++cnt1]=id[i];
else q2[++cnt2]=id[i],cur[id[i]]=num;
}
for(int i=l;i<=mid;i++)add(mat[i].x,mat[i].y,-1);
int qcnt=ql;
for(int i=1;i<=cnt1;i++)id[qcnt++]=q1[i];
for(int i=1;i<=cnt2;i++)id[qcnt++]=q2[i];
Solve(l,mid,ql,ql+cnt1-1);
Solve(mid+1,r,ql+cnt1,qr);
}
void solve(){
//start
cin.tie(0)->ios::sync_with_stdio(0);
cout.tie(0);
cin>>n>>cas;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
mat[get(i,j)]={i,j,x};
}
}
sort(mat+1,mat+n*n+1);
for(int i=1;i<=cas;i++){
cin>>q[i].x_1>>q[i].y_1>>q[i].x_2>>q[i].y_2>>q[i].k;
id[i]=i;
}
Solve(1,n*n,1,cas);
for(int i=1;i<=cas;i++)cout<<ans[i]<<endl;
}
int main(){
solve();
return 0;
}
暂无评论