本文主要是介绍天使玩偶 [CDQ分治]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
我们可以将这些操作看成(x,y,t) 三元组 , 表示x,y坐标 , 与时间
CDQ 分治时 将前一半时间的修改提出来 , 再将后一半时间的询问提出来
然后按x 排序 , 这样就是一个二维偏序了 , 但是有一个问题 , 我们如何求dis
发现可以分4种情况 , 这里拿左下举个例子
我们发现
于是 x 按顺序插入 , 在树状数组的y 的位置插入(xi + yi) , 询问就是x+y - Q(y)
其余3种情况同理 , 注意x 的插入顺序
还是一句话 , 一维(时间) CDQ 可以忽略掉 , 二维(x) 排序可以搞掉 , 三维(y) 就用树状数组
#include<bits/stdc++.h>
#define N 2000050
#define inf 0x3fffffff
using namespace std;
struct Node{int x,y,id,op;}q[N],tmp[N];
int n,m,c[N],maxy,ans[N];
bool cmp(Node a,Node b){if(a.x==b.x) return a.y<b.y;return a.x<b.x;
}
void Up(int x,int val){for(;x<=maxy;x+=x&-x) c[x] = max(c[x],val);}
int Q(int x){int ans=-inf; for(;x;x-=x&-x) ans = max(ans,c[x]); return ans;}
void CDQ(int L,int R){if(L>=R) return;int mid = (L+R) >> 1;CDQ(L,mid) , CDQ(mid+1,R);int cnt = 0;for(int i=L;i<=mid;i++) if(q[i].op == 1) tmp[++cnt] = q[i];for(int i=mid+1;i<=R;i++) if(q[i].op == 2) tmp[++cnt] = q[i];sort(tmp+1,tmp+cnt+1,cmp);// 左下 for(int i=1;i<=cnt;i++){if(tmp[i].op == 1) Up(tmp[i].y, tmp[i].x+tmp[i].y);else ans[tmp[i].id] = min(ans[tmp[i].id], tmp[i].x + tmp[i].y - Q(tmp[i].y));} for(int i=1;i<=cnt;i++) if(tmp[i].op == 1)for(int x = tmp[i].y; x<=maxy; x+=x&-x) c[x] = -inf;// 右下 for(int i=cnt;i>=1;i--){if(tmp[i].op == 1) Up(tmp[i].y, tmp[i].y-tmp[i].x);else ans[tmp[i].id] = min(ans[tmp[i].id], tmp[i].y - tmp[i].x - Q(tmp[i].y));} for(int i=1;i<=cnt;i++) if(tmp[i].op == 1)for(int x = tmp[i].y; x<=maxy; x+=x&-x) c[x] = -inf;// 左上 for(int i=1;i<=cnt;i++){if(tmp[i].op == 1) Up(maxy - tmp[i].y, tmp[i].x-tmp[i].y);else ans[tmp[i].id] = min(ans[tmp[i].id], tmp[i].x - tmp[i].y - Q(maxy - tmp[i].y)); }for(int i=1;i<=cnt;i++) if(tmp[i].op == 1)for(int x = maxy-tmp[i].y; x<=maxy; x+=x&-x) c[x] = -inf;// 右上 for(int i=cnt;i>=1;i--){if(tmp[i].op == 1) Up(maxy - tmp[i].y, -tmp[i].y - tmp[i].x);else ans[tmp[i].id] = min(ans[tmp[i].id], -tmp[i].x - tmp[i].y - Q(maxy - tmp[i].y));} for(int i=1;i<=cnt;i++) if(tmp[i].op == 1)for(int x = maxy-tmp[i].y; x<=maxy; x+=x&-x) c[x] = -inf;
}
int main(){scanf("%d%d",&n,&m); for(int i=1;i<=N-50;i++) ans[i] = inf , c[i] = -inf;for(int i=1;i<=n;i++){scanf("%d%d",&q[i].x,&q[i].y);q[i].id = i; q[i].op = 1; // 添加maxy = max(maxy, q[i].y);}for(int i=n+1;i<=m+n;i++){scanf("%d%d%d",&q[i].op,&q[i].x,&q[i].y);q[i].id = i; maxy = max(maxy, q[i].y);} maxy ++; CDQ(1,n+m); for(int i=n+1;i<=m+n;i++) if(q[i].op==2) printf("%d\n",ans[i]);
}
这篇关于天使玩偶 [CDQ分治]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
