BZOJ 2716 Violet 3 天使玩偶 CDQ分治

BZOJ 2716 Violet 3 天使玩偶 CDQ分治

题目大意：初始给定平面上的一个点集，提供两种操作：

1.将一个点加入点集

2.查询距离一个点最小的曼哈顿距离

K-D树是啥。。。不会写。。。我只会CDQ分治

对于一个询问，查询的点与这个点的位置关系有四种，我们现在只讨论左下角，剩余三个象限同理

设询问的点为(x,y)，查询的点为(x',y')

则dis=(x-x')+(y-y')=(x+y)-(x'+y')

于是我们要找到查询的点左下方所有点中x'+y'最大的点，x值排序，y值维护树状数组即可

用CDQ分治化在线为离线，保证x有序即可

其它三个象限同理 记得讨论的时候别写差了 仔细检查一下为好

此题80s真吓人。。。不过完全没有那么慢，无论是K-DTree还是CDQ分治都是半分钟解决问题。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 500500
using namespace std;
struct point{int x,y;bool operator < (const point &p) const{return x < p.x;}
}points[M];
struct abcd{int p,x,y,pos,dis;bool operator < (const abcd &z) const{if( x == z.x )return pos < z.pos;return x < z.x;}
}q[M],nq[M];
int n,m,tot,maxnum;
int c[1001001],tim[1001001];
inline int getc() {  static const int L = 1 << 15;  static char buf[L], *S = buf, *T = buf;  if (S == T) {  T = (S = buf) + fread(buf, 1, L, stdin);  if (S == T)  return EOF;  }  return *S++;  
}  
inline int getint() {  int c;  while(!isdigit(c = getc()) && c != '-');  bool sign = c == '-';  int tmp = sign ? 0 : c - '0';  while(isdigit(c = getc()))  tmp = (tmp << 1) + (tmp << 3) + c - '0';  return sign ? -tmp : tmp;  
}  
inline void output(int x)   
{  static int a[20];  if (x == 0)  putchar('0');  else {  int top = 0;  if (x < 0)  putchar('-'), x=-x;  while(x) {  a[++top] = x % 10;  x /= 10;  }  for(int i = top; i >= 1; --i)  putchar('0' + a[i]);  }  puts("");  
}
void Update(int x,int y,int flag)
{for(;x&&x<=maxnum;x+=(x&-x)*flag){if(tim[x]!=tot)c[x]=0xefefefef,tim[x]=tot;c[x]=max(c[x],y);}
}
int Get_Ans(int x,int flag)
{int re=0xefefefef;for(;x&&x<=maxnum;x+=(x&-x)*flag)if(tim[x]==tot)re=max(re,c[x]);return re;
}
void CDQ(int l,int r)
{int i,j,mid=l+r>>1;int l1=l,l2=mid+1;if(l==r){if(q[mid].p==2)output(q[mid].dis);return ;}for(i=l;i<=r;i++){if(q[i].pos<=mid)nq[l1++]=q[i];elsenq[l2++]=q[i];}memcpy( q+l , nq+l , sizeof(q[0])*(r-l+1) );CDQ(l,mid);for(++tot,j=l,i=mid+1;i<=r;i++)if(q[i].p==2){for(;j<=mid&&q[j].x<=q[i].x;j++)if(q[j].p==1)Update(q[j].y,q[j].x+q[j].y,1);q[i].dis=min(q[i].dis,q[i].x+q[i].y-Get_Ans(q[i].y,-1) );}for(++tot,j=l,i=mid+1;i<=r;i++)if(q[i].p==2){for(;j<=mid&&q[j].x<=q[i].x;j++)if(q[j].p==1)Update(q[j].y,q[j].x-q[j].y,-1);q[i].dis=min(q[i].dis,q[i].x-q[i].y-Get_Ans(q[i].y,1) );}for(++tot,j=mid,i=r;i>mid;i--)if(q[i].p==2){for(;j>=l&&q[j].x>=q[i].x;j--)if(q[j].p==1)Update(q[j].y,q[j].y-q[j].x,1);q[i].dis=min(q[i].dis,q[i].y-q[i].x-Get_Ans(q[i].y,-1) );}for(++tot,j=mid,i=r;i>mid;i--)if(q[i].p==2){for(;j>=l&&q[j].x>=q[i].x;j--)if(q[j].p==1)Update(q[j].y,-q[j].x-q[j].y,-1);q[i].dis=min(q[i].dis,-q[i].x-q[i].y-Get_Ans(q[i].y,1) );}CDQ(mid+1,r);l1=l;l2=mid+1;for(i=l;i<=r;i++){if(q[l1]<q[l2]&&l1<=mid||l2>r)nq[i]=q[l1++];elsenq[i]=q[l2++];}memcpy( q+l , nq+l , sizeof(q[0])*(r-l+1) );
}
int main()
{int i,j;cin>>n>>m;for(i=1;i<=n;i++){points[i].x=getint();points[i].y=getint();++points[i].x;++points[i].y;maxnum=max(maxnum,points[i].y);}sort(points+1,points+n+1);for(i=1;i<=m;i++){q[i].p=getint();q[i].x=getint();q[i].y=getint();++q[i].x;++q[i].y;q[i].pos=i;q[i].dis=0x3f3f3f3f;maxnum=max(maxnum,q[i].y);}sort(q+1,q+m+1);for(++tot,j=1,i=1;i<=m;i++)if(q[i].p==2){for(;j<=n&&points[j].x<=q[i].x;j++)Update(points[j].y,points[j].x+points[j].y,1);q[i].dis=min(q[i].dis,q[i].x+q[i].y-Get_Ans(q[i].y,-1) );}for(++tot,j=1,i=1;i<=m;i++)if(q[i].p==2){for(;j<=n&&points[j].x<=q[i].x;j++)Update(points[j].y,points[j].x-points[j].y,-1);q[i].dis=min(q[i].dis,q[i].x-q[i].y-Get_Ans(q[i].y,1) );}for(++tot,j=n,i=m;i;i--)if(q[i].p==2){for(;j&&points[j].x>=q[i].x;j--)Update(points[j].y,points[j].y-points[j].x,1);q[i].dis=min(q[i].dis,q[i].y-q[i].x-Get_Ans(q[i].y,-1) );}for(++tot,j=n,i=m;i;i--)if(q[i].p==2){for(;j&&points[j].x>=q[i].x;j--)Update(points[j].y,-points[j].x-points[j].y,-1);q[i].dis=min(q[i].dis,-q[i].x-q[i].y-Get_Ans(q[i].y,1) );}CDQ(1,m);return 0;
}