盘锦市建设局网站地址,浙江城乡与住房建设部网站,金融 网站 模板,凡科建站有哪些弊端正题
题目链接:https://www.ybtoj.com.cn/contest/66/problem/4 题目大意
平面上nnn个红点#xff0c;nnn个蓝点#xff0c;对于没一个红点求一个与它纵坐标距离不超过ddd的一个点与它的曼哈顿距离最短。 解题思路
一个点分为两种情况#xff0c;在询问点左边的红点要求横…正题
题目链接:https://www.ybtoj.com.cn/contest/66/problem/4 题目大意
平面上nnn个红点nnn个蓝点对于没一个红点求一个与它纵坐标距离不超过ddd的一个点与它的曼哈顿距离最短。 解题思路
一个点分为两种情况在询问点左边的红点要求横坐标大在询问点右边的红点要求横坐标小为了方便我们开两个线段树。
依次从上往下扫描点然后将蓝点加入两个线段树中注意扫描位置变换时我们要让所有加入的点的值加上一个移动的距离即纵坐标的距离差。然后因为要把加入的超出范围的点弹出去所以我们在线段树的每个叶子处维护一个堆即可。
然后正反各扫一次即可。
因为叶子处维护所以堆和线段树实际复杂度是分开的时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1e510,Lim1e8,inf1e9;
struct point{int x,y,dl,dr;
}a[N],b[N];
int n,d,cnt,c[N1],ans[N];
struct Heap{priority_queueint q1,q2;void push(int x){q1.push(x);return;}void pop(int x){q2.push(x);return;}bool empty(){return (q1.size()-q2.size())0;}int top(){while(!q2.empty()q1.top()q2.top())q1.pop(),q2.pop();return q1.top();}void clear(){while(!q1.empty())q1.pop();while(!q2.empty())q2.pop();return;}
};
struct node{Heap q[N3];int w[N3],lazy[N3];void Clear(){for(int i1;iN3;i)w[i]-inf,lazy[i]0,q[i].clear();}void Downdata(int x){if(!lazy[x])return;lazy[x*2]lazy[x];lazy[x*21]lazy[x];w[x*2]lazy[x];w[x*21]lazy[x];lazy[x]0;return;}void Push(int x,int l,int r,int pos,int val){if(lr){val-lazy[x];q[x].push(val);if(!q[x].empty())w[x]q[x].top()lazy[x];else w[x]-inf;return;}int mid(lr)1;Downdata(x);if(posmid)Push(x*2,l,mid,pos,val);else Push(x*21,mid1,r,pos,val);w[x]max(w[x*2],w[x*21]);return;}void Pop(int x,int l,int r,int pos,int val){if(lr){q[x].pop(val);if(!q[x].empty())w[x]q[x].top()lazy[x];else w[x]-inf;return;}int mid(lr)1;Downdata(x);if(posmid)Pop(x*2,l,mid,pos,val);else Pop(x*21,mid1,r,pos,val);w[x]max(w[x*2],w[x*21]);return;} int Ask(int x,int L,int R,int l,int r){if(lr)return -inf; if(LlRr)return w[x];int mid(LR)1;Downdata(x);if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return max(Ask(x*2,L,mid,l,mid),Ask(x*21,mid1,R,mid1,r)); }
}Tl,Tr;
bool cmp(point x,point y)
{return x.xy.x;}
void work(){sort(a1,a1n,cmp);sort(b1,b1n,cmp);int l1,r1;Tl.Clear();Tr.Clear();for(int i1;in;i){if(i!1){Tl.lazy[1]-b[i].x-b[i-1].x;Tr.lazy[1]-b[i].x-b[i-1].x;Tl.w[1]-b[i].x-b[i-1].x;Tr.w[1]-b[i].x-b[i-1].x;}while(rna[r].xb[i].x){int wlower_bound(c1,c1cnt,a[r].y)-c;Tl.Push(1,1,cnt,w,a[r].dla[r].y-b[i].xa[r].x);Tr.Push(1,1,cnt,w,a[r].drLim-a[r].y-b[i].xa[r].x);r;}while(lnb[i].x-a[l].xd){int wlower_bound(c1,c1cnt,a[l].y)-c;Tl.Pop(1,1,cnt,w,a[l].dl);Tr.Pop(1,1,cnt,w,a[l].dr);l;}int wlower_bound(c1,c1cnt,b[i].y)-c;ans[b[i].dl]min(ans[b[i].dl],b[i].y-Tl.Ask(1,1,cnt,1,w));ans[b[i].dl]min(ans[b[i].dl],Lim-Tr.Ask(1,1,cnt,w1,cnt)-b[i].y);}
}
int main()
{freopen(portal.in,r,stdin);freopen(portal.out,w,stdout);scanf(%d%d,n,d);for(int i1;in;i)scanf(%d%d,b[i].x,b[i].y),b[i].dli,swap(b[i].x,b[i].y),c[in]b[i].y;for(int i1;in;i)scanf(%d%d,a[i].x,a[i].y),swap(a[i].x,a[i].y),c[i]a[i].y;sort(c1,c12*n);memset(ans,0x3f3f3f3f,sizeof(ans));cntunique(c1,c12*n)-c-1;work();for(int i1;in;i)a[i].xLim-a[i].x,b[i].xLim-b[i].x;work();for(int i1;in;i)if(ans[i]1e9)printf(0\n);else printf(%d\n,ans[i]);return 0;
}
