首页 > 代码库 > BZOJ 2716: [Violet 3]天使玩偶 [CDQ分治]
BZOJ 2716: [Violet 3]天使玩偶 [CDQ分治]
传送门
题意：
维护二维点集P，支持以下两个操作
(1)插入点(x,y)
(2)给定询问(x,y)，求点集中离询问点最近的点
距离定义为曼哈顿距离
Dis(P1,P2)=|x1-x2|+|y1-y2|
n,m<=500000
x,y<=1000000
时间，$x$，$y$
$CDQ$分治里需要四个象限分类讨论，树状数组维护最大值
然后有两个象限是后缀和
然后跟$PoPoQQQ$学了一个神奇的技巧，树状数组加一个时间戳，就可以不用每次清空之前的操作了
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long ll;const int N=1e6+5,M=1e6+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int cc[20];inline void put(int x){ if(x==0) putchar(‘0‘); else{ int top=0; while(x) cc[++top]=x%10,x/=10; for(int i=top;i>=1;i--) putchar(‘0‘+cc[i]); } putchar(‘\n‘);}int n,m,qid,maxVal=-INF;struct Operation{ int x,y,op,id,qid; Operation():op(0){}}a[N],t[N];int c[M],mark[M],cl;inline int lowbit(int x){return x&-x;}inline void upd(int p,int v){ for(;p<=maxVal;p+=lowbit(p)){ if(mark[p]!=cl) mark[p]=cl,c[p]=v; else c[p]=max(c[p],v); }}inline int que(int p){ int re=-INF; for(;p;p-=lowbit(p)) if(mark[p]==cl) re=max(re,c[p]); return re;}inline void upd2(int p,int v){ for(;p;p-=lowbit(p)){ if(mark[p]!=cl) mark[p]=cl,c[p]=v; else c[p]=max(c[p],v); }}inline int que2(int p){ int re=-INF; for(;p<=maxVal;p+=lowbit(p)) if(mark[p]==cl) re=max(re,c[p]); return re;}int ans[N];void sol(int l,int r){//printf("sol %d %d\n",l,r); int mid=(l+r)>>1; cl++; for(int i=l;i<=r;i++){ if(!a[i].op&&a[i].id<=mid) upd(a[i].y,a[i].x+a[i].y); else if(a[i].op&&a[i].id>mid) ans[a[i].qid]=min(ans[a[i].qid],a[i].x+a[i].y-que(a[i].y)); } cl++; for(int i=l;i<=r;i++){ if(!a[i].op&&a[i].id<=mid) upd2(a[i].y,a[i].x-a[i].y); else if(a[i].op&&a[i].id>mid) ans[a[i].qid]=min(ans[a[i].qid],a[i].x-a[i].y-que2(a[i].y)); } cl++; for(int i=r;i>=l;i--){ if(!a[i].op&&a[i].id<=mid) upd(a[i].y,a[i].y-a[i].x); else if(a[i].op&&a[i].id>mid) ans[a[i].qid]=min(ans[a[i].qid],a[i].y-a[i].x-que(a[i].y)); } cl++; for(int i=r;i>=l;i--){ if(!a[i].op&&a[i].id<=mid) upd2(a[i].y,-a[i].y-a[i].x); else if(a[i].op&&a[i].id>mid) ans[a[i].qid]=min(ans[a[i].qid],-a[i].y-a[i].x-que2(a[i].y)); } //for(int i=1;i<=qid;i++) printf("%d ",ans[i]);puts("end");}void CDQ(int l,int r){//printf("CDQ %d %d\n",l,r); if(l==r) return; int mid=(l+r)>>1; CDQ(l,mid);CDQ(mid+1,r); int i=l,j=mid+1,p=l; while(i<=mid||j<=r){ if(j>r||(i<=mid&&a[i].x<=a[j].x)) t[p++]=a[i++]; else t[p++]=a[j++]; } for(int i=l;i<=r;i++) a[i]=t[i]; sol(l,r);}int main(){ freopen("in","r",stdin); //freopen("out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++){ a[i].x=read()+1,a[i].y=read()+1,a[i].id=i; maxVal=max(maxVal,max(a[i].x,a[i].y)); } for(int i=1;i<=m;i++){ a[++n].op=read()-1,a[n].x=read()+1,a[n].y=read()+1,a[n].id=n; if(a[n].op) a[n].qid=++qid; maxVal=max(maxVal,max(a[n].x,a[n].y)); } //for(int i=n-m+1;i<=n;i++) printf("check %d %d %d %d\n",i,a[i].x,a[i].y,a[i].qid); //printf("n %d %d %d\n",n,qid,maxVal); for(int i=1;i<=qid;i++) ans[i]=INF; CDQ(1,n); for(int i=1;i<=qid;i++) put(ans[i]);}
BZOJ 2716: [Violet 3]天使玩偶 [CDQ分治]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。