开始给出平面上\(n\)个点，\(m\)个操作，每次加一个点或者查询一个点的曼哈顿距离最近点的曼哈顿距离。（坐标为整数）。
\(n,m\le 5\times 10^5\)。
分析
首先KD-Tree的做法是错误的，一个经典的例子是给出\(n\)个点的圆，询问圆心。
如果这个问题是只统计一个角方向（一个点左下方，右下方，右上方，左上方的曼哈顿距离最近点）的，那么可以排序加线段树解决。又因为这个问题满足加法，所以我们对每个方向做一次就好啦。
那动态插入怎么办呢？使用cdq分治，每次统计前一半的点对后一半的询问的贡献，由于满足加法，所以可以这样做。
复杂度为\(O(nlog^2n)\)。
由于是角方向，所以可以发现查询总是查询\([1,r]\)或者\([l,max]\)之间的最小值，所以可以维护两个相反的树状数组来代替常数大的线段树。
代码
没有办法再优化了，还是过不了啊！！精神上过了。
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<sys/mman.h>
#include<sys/stat.h>
#define lowbit(x) (x&-x)
struct BufferedInputStream {
char *buf,*p;
int size;
inline void init() {
register int fd=fileno(stdin);
struct stat sb;
fstat(fd, &sb);
size=sb.st_size;
buf=reinterpret_cast<char *>(mmap(0, size, PROT_READ, MAP_PRIVATE, fileno(stdin), 0));
p=buf;
}
inline char gchar() {
return (p==buf+size || *p==-1)?-1:*p++;
}
} str;
using std::sort;
using std::fill;
inline int read() {
register int x=0,f=1;
register char c=str.gchar();
for (;!isdigit(c);c=str.gchar()) if (c=='-') f=-1;
for (;isdigit(c);c=str.gchar()) x=x*10+c-'0';
return x*f;
}
inline void write(int &x) {
if (!x) putchar('0'); else {
static char s[15];
register int tot=0;
while (x) s[++tot]=x%10+'0',x/=10;
while (tot) putchar(s[tot--]);
}
putchar('\n');
}
const int maxn=2.1e6+10;
const int maxp=1e6+10;
const int inf=1e8+10;
struct node {
int x,y;
node (int x=0,int y=0):x(x),y(y) {}
inline bool operator == (const node &a) const {return x==a.x && y==a.y;}
inline bool operator < (const node &a) const {return y==a.y?x<a.x:y<a.y;}
};
struct Q {
int tp,id;
node p;
} a[maxn],b[maxn];
inline bool cmp1(const Q &a,const Q &b) {
return a.p==b.p?a.tp<b.tp:a.p<b.p;
}
inline bool cmp2(const Q &a,const Q &b) {
return a.p==b.p?a.tp>b.tp:a.p<b.p;
}
inline int min(const int &x,const int &y) {return x<y?x:y;}
inline void Min(int &x,const int y) {
x=min(x,y);
}
int ans[maxn],n,m;
struct BIT {
struct array {
int a[maxp],t[maxp],clc;
inline int & operator [] (const int &x) {
if (t[x]!=clc) t[x]=clc,a[x]=inf;
return a[x];
}
} a,b;
BIT () {clr();}
inline void clr() {
++a.clc;
++b.clc;
}
inline void insert(int p,const int d) {
for (register int i=p;i<maxp;i+=lowbit(i)) Min(a[i],d);
p=maxp-p;
for (register int i=p;i<maxp;i+=lowbit(i)) Min(b[i],d);
}
inline int query(int l,const int r) {
register int ret=inf;
if (l==1) {
for (register int i=r;i;i-=lowbit(i)) Min(ret,a[i]);
} else if (r==maxp-1) {
l=maxp-l;
for (register int i=l;i;i-=lowbit(i)) Min(ret,b[i]);
}
return ret;
}
} sgt;
void solve(const int l,const int r) {
if (l==r) return;
register int mid=(l+r)>>1,all=0;
solve(l,mid);
solve(mid+1,r);
for (register int i=l;i<=mid;++i) if (!a[i].tp) b[++all]=a[i];
for (register int i=mid+1;i<=r;++i) if (a[i].tp) b[++all]=a[i];
sort(b+1,b+all+1,cmp1);
sgt.clr();
for (register int i=1,j;i<=all;i=j+1) {
for (j=i;j<all && b[j+1].p.y==b[i].p.y;++j);
for (register int k=i;k<=j;++k) if (!b[k].tp) sgt.insert(b[k].p.x,-b[k].p.x-b[k].p.y); else
Min(ans[b[k].id],b[k].p.x+b[k].p.y+sgt.query(1,b[k].p.x));
}
sgt.clr();
for (register int i=all,j;i;i=j-1) {
for (j=i;j>1 && b[j-1].p.y==b[i].p.y;--j);
for (register int k=j;k<=i;++k) if (!b[k].tp) sgt.insert(b[k].p.x,b[k].p.y-b[k].p.x); else
Min(ans[b[k].id],b[k].p.x-b[k].p.y+sgt.query(1,b[k].p.x));
}
sort(b+1,b+all+1,cmp2);
sgt.clr();
for (register int i=1,j;i<=all;i=j+1) {
for (j=i;j<all && b[j+1].p.y==b[i].p.y;++j);
for (register int k=j;k>=i;--k) if (!b[k].tp) sgt.insert(b[k].p.x,b[k].p.x-b[k].p.y); else
Min(ans[b[k].id],b[k].p.y-b[k].p.x+sgt.query(b[k].p.x,maxp-1));
}
sgt.clr();
for (register int i=all,j;i;i=j-1) {
for (j=i;j>1 && b[j-1].p.y==b[i].p.y;--j);
for (register int k=i;k>=j;--k) if (!b[k].tp) sgt.insert(b[k].p.x,b[k].p.x+b[k].p.y); else
Min(ans[b[k].id],-b[k].p.x-b[k].p.y+sgt.query(b[k].p.x,maxp-1));
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("my.out","w",stdout);
#endif
str.init();
n=read(),m=read();
fill(ans+1,ans+m+1,inf);
for (register int i=1;i<=n;++i) {
int x=read()+1,y=read()+1;
a[i]=(Q){0,0,node(x,y)};
}
for (register int i=1;i<=m;++i) {
int tp=read()-1,x=read()+1,y=read()+1;
a[i+n]=(Q){tp,i,node(x,y)};
}
solve(1,n+m);
for (register int *i=ans+1,*ed=ans+m+1;i!=ed;++i) if (*i<=(int)2e6) write(*i);
return 0;
}
转播
