不递归求解的方法就是按mid从小到大排序,可是我只有50分,大佬看看为什么求求了
#include <bits/stdc++.h>
using namespace std;
const int N=5e2+5;
struct Point{
int x,y,l,r,k;
int xl,xr,mid;
int id;
}wt[100005];
struct zb{
int x,y;
};
vector <zb> e[N*N];
int a[N][N],ans[100005],n,m,q,b[N*N],len,c[N][N],cnt;
void add(int x,int y){
for(int i = x;i<=n;i+=i&(-i))
for(int j = y;j <= n;j+=j&(-j))
c[i][j]++;
}
int query(int x,int y){
int ans=0;
for(int i = x;i;i-=i&(-i))
for(int j = y;j;j-=j&(-j))
ans+=c[i][j];
return ans;
}
int queryans(int x,int y,int l,int r){
return query(l,r)-query(l,y-1)-query(x-1,r)+query(x-1,y-1);
}
int find(int x){
return lower_bound(b+1,b+1+cnt,x)-b;
}
bool cmp(Point x,Point y){
return x.mid<y.mid;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
cin >> a[i][j];
b[++cnt]=a[i][j];
}
}
sort(b+1,b+1+cnt);
len=unique(b+1,b+1+cnt)-b-1;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
a[i][j]=find(a[i][j]);
e[a[i][j]].push_back((zb){i,j});
}
}
for(int i = 1;i <= q;i++){
cin >> wt[i].x >> wt[i].y >> wt[i].l >> wt[i].r >> wt[i].k;
wt[i].id=i;
wt[i].xl=1,wt[i].xr=len;
}
int logn=log2(len)+1;
while(logn--){
for(int i = 1;i <= q;i++)wt[i].mid=(wt[i].xl+wt[i].xr)>>1;
memset(c,0,sizeof(c));
sort(wt+1,wt+1+q,cmp);
int now=1;
for(int i = 1;i <= q;i++){
while(now<=wt[i].mid){
for(int j = 0;j < e[now].size();j++)add(e[now][j].x,e[now][j].y);
now++;
}
int num=queryans(wt[i].x,wt[i].y,wt[i].l,wt[i].r);
if(num<wt[i].k)wt[i].xl=wt[i].mid+1;
else{
ans[wt[i].id]=b[wt[i].mid];
wt[i].xr=wt[i].mid-1;
}
}
}
for(int i = 1;i <= q;i++)cout << ans[i] << "\n";
return 0;
}