论整体二分法的不递归求解
查看原帖
论整体二分法的不递归求解
961149
xiao7_Mr_10_楼主2024/3/3 16:17

不递归求解的方法就是按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;
}
2024/3/3 16:17
加载中...