NOIP2023模拟7联测28 花之舞

本文主要是介绍NOIP2023模拟7联测28 花之舞，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

有一个花园，每朵花可以表示为平面直角坐标系上的 $N$ 个点，第 $i$ 个点的坐标为 $O(x_i,y_i)$ 。定义两朵花之间的距离为它们的切比雪夫距离，即 $dis(u,v)=\max(|x_u-x_v|,|y_u-y_v|)$ 。

有 $q$ 个询问，第 $i$ 个询问为一个区间 $l_i,r_i]$ ，请确定一个 $k(l\leq k\leq r)$ ，最大化 $\min\limits_{1\leq u<v\leq r,u\neq k,v\neq k}dis(u,v)$ 。即，最大化：删掉一朵花后，区间里花之间距离最小值。

$3\leq n\leq 3\times 10^4,1\leq q\leq 3\times 10^5,1\leq x_i,y_i\leq 10^8$

$1\leq l_i<r_i\leq n,r_i-l_i\geq 2$

保证不存在重合的点。

时间限制 $4000 m s$ ，空间限制 $1024 MB$ 。

题解

显然，要最大化任意两点的最小值，最近点对的两个点必须删一个。那么，我们可以想办法求出所有在询问中可能用到的最近点对。

枚举 $k$ （ $0\leq k\leq \log v$ ，其中 $v$ 为值域），将平面直角坐标系分为大小为 $2^k\times 2^k$ 的矩阵。对于每个 $k$ ，我们考虑求所有距离在 $2^{k-1},2^k)$ 上的点对（当然，求这个的目的是求出所有在询问中可能用到的最近点对，得到距离小于 $2^{k-1}$ 的点对也无妨）。对于每个矩阵，找到相邻矩阵（相邻指共边或共顶点，也就是八连通）和自己的矩阵，对这九个矩阵分别进行操作。每次操作就是将这两个矩阵（自己和操作对象）的点按编号从小到大排序。这自己的矩阵为 $A$ ，操作对象的矩阵为 $B$ ，则对于 $A$ 中的每个点 $x$ ，在 $B$ 中找到最小的点 $y$ 且 $y\geq x$ （注意 $x, y$ 是编号），将 $z\in [\max(0,y-8),y-1]$ 的点都存储在 $x$ 的 $v ec t or$ 中，表示 $x$ 和 $z$ 可能在询问中构成最近点对。

为什么要取 $z\in[\max(0,y-8),y-1]$ 呢？因为如果 $B$ 中要取到 $z^{'}$ ，使得 $z'<\max(0,y-8)$ 且 $z^{'}$ 和 $x$ 可能构成最近点对，则能让其构成最近点对的区间可定是包含 $[z^{'}, x]$ 的。既然当前枚举的是距离在 $2^{k-1},2^k)$ 上的点对，则如果 $B$ 中存在 $z\in [\max(0,y-8),y-1]$ 和 $z^{'}$ 的距离小于 $2^{k-1}$ ，则 $z$ 和 $z^{'}$ 的距离一定比 $x$ 和 $z^{'}$ 的距离小，也就是说只要询问包含 $x$ 和 $z^{'}$ ，则最近点对一定是 $z$ 和 $z^{'}$ ，也就是说 $x$ 和 $z^{'}$ 不可能在询问中构成最近点对。

我们发现，在最坏情况下，在 $B$ 中取 $6$ 个点之后，不管怎么加点，都会使得存在两个点的距离小于 $2^{k-1}$ 。考虑到后面要删一个点，所以就取到 $7$ 到 $8$ 为宜，所以上面取的区间为 $[\max(0,y-8),y-1]$ 。最后还要对每个点的 $v ec t or$ 去重。

然后我们考虑询问怎么做。我们可以依照询问右边界升序扫描线，将可能的最近点对插入到线段树中。下面称上面处理出来的可能在询问中用到的最近点对为支配点对。

线段树的每个节点只考虑左端点在节点对应的区间里且右端点不超过当前扫描到的边界的支配点对，维护几个值，分别是：

这些支配点对里，最近点对是哪对，距离是多少
分别删掉上一条中最近点对中的一个点后的最近点对距离

合并区间的时候，设两边最近点对分别是 $u_1,v_1)$ 和 $u_2,v_2)$ ，其中 $u_1<u_2$ 。如果两边最近点对有共同端点，就可以将删掉这个共同端点后的最近点对距离更新为两边最小值；如果两边最近点对没有共同端点，那么一边的最近点对可能更新另一边的删掉某点后的最近点对距离。

询问时考虑删掉最近点对的哪个点，取最优即可。

时间复杂度为 $O(n\log n\log v+q\log n)$ ，其中 $v$ 为 $x_i,y_i$ 的值域。常数比较大，但时限有 $5000 m s$ ，是可以过的。

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const int N=30000,Q=300000,inf=2100000000;
int n,q,x[N+5],y[N+5],ans[Q+5];
vector<int>w[N+5];
vector<pair<int,int>>g[N+5];
map<pair<int,int>,vector<int>>mp;
struct node{int mn,x,y,v1,v2;
}tr[4*N+5];
int dis(int i,int j){return max(abs(x[i]-x[j]),abs(y[i]-y[j]));
}
void build(int k,int l,int r){tr[k]=(node){inf,-1,-1,inf,inf};if(l==r) return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);
}
node merge(node a,node b){node re;int v1,v2;if(a.mn<b.mn){v1=min(a.v1,b.mn);v2=a.v2;if(a.y==b.y) v2=min(v2,b.v2);else if(a.y==b.x) v2=min(v2,b.v1);else v2=min(v2,b.mn);re=(node){a.mn,a.x,a.y,v1,v2};}else{v1=b.v1;v2=b.v2;if(b.x==a.y) v1=min(v1,a.v2);else v1=min(v1,a.mn);if(b.y==a.y) v2=min(v2,a.v2);else v2=min(v2,a.mn);re=(node){b.mn,b.x,b.y,v1,v2};}return re;
}
void ch(int k,int l,int r,int x,int y){if(l==r&&l==x){int d=dis(x,y);if(d<tr[k].mn) tr[k]=(node){d,x,y,inf,tr[k].mn};else if(d<tr[k].v2) tr[k].v2=d;return;}int mid=l+r>>1;if(x<=mid) ch(lc,l,mid,x,y);else ch(rc,mid+1,r,x,y);tr[k]=merge(tr[lc],tr[rc]);
}
node find(int k,int l,int r,int x,int y){if(l>=x&&r<=y) return tr[k];int mid=l+r>>1;if(y<=mid) return find(lc,l,mid,x,y);if(x>mid) return find(rc,mid+1,r,x,y);return merge(find(lc,l,mid,x,y),find(rc,mid+1,r,x,y));
}
int main()
{freopen("flower.in","r",stdin);freopen("flower.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);for(int dv=0;dv<=27;dv++){mp.clear();for(int i=1;i<=n;i++){mp[{x[i]>>dv,y[i]>>dv}].push_back(i);}for(auto pv:mp){const auto &p=pv.first;const auto &v=pv.second;for(int dx=-1;dx<=1;dx++){for(int dy=-1;dy<=1;dy++){auto it=mp.find({p.first+dx,p.second+dy});if(it==mp.end()) continue;const auto &v1=it->second;for(int i=0,j=0;i<v.size();i++){while(j<v1.size()&&v1[j]<v[i]) ++j;for(int k=max(0,j-8);k<j;k++){w[v[i]].push_back(v1[k]);}}}}}}for(int i=1;i<=n;i++){sort(w[i].begin(),w[i].end());w[i].erase(unique(w[i].begin(),w[i].end()),w[i].end());}scanf("%d",&q);for(int i=1,l,r;i<=q;i++){scanf("%d%d",&l,&r);g[r].push_back({l,i});}build(1,1,n);for(int i=1;i<=n;i++){for(auto l:w[i]) ch(1,1,n,l,i);for(auto k:g[i]){int l=k.first,id=k.second;node re=find(1,1,n,l,i);ans[id]=max(re.v1,re.v2);}}for(int i=1;i<=q;i++) printf("%d\n",ans[i]);return 0;
}