天使玩偶

题意：有两种操作：

  1. 给二维平面上加入一个点
  2. 询问二维平面上到某个点最近的一个点（用曼哈顿距离来表示）

思路：标准的CDQ分治，离线处理两种操作

  1. 当想到CDQ分治后本题的重点在于如何处理曼哈顿距离，毕竟看到绝对值都头疼
  2. 我们最希望的是能去掉绝对值！这里有一种处理方法：我们只考虑每个询问点左下角的点，则显然可以去掉绝对值，用普通的CDQ分治，按照 x x x坐标排序，按照 y y y坐标将 x + y x+y x+y插入树状数组，并求出每个询问点左下角最大的 x + y x+y x+y的值，就可以求出这种情况的解
  3. 对于另外三种情况，分别将 x x x， y y y进行倒置（细节见代码），也就是一共跑四遍CDQ分治即可
  4. 当然还有一些优化，比如每次CDQ以前，先将完全不可能在任何询问左下角的点给删掉；还有 m a x , m i n max,min max,min的加速。

放个原题描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 6e5+10;
const int mod = 2e9+7;
const double eps = 1e-9;
const int maxx = 2e6+10;

struct P{
    int f, x, y, id;
    P() {}
    P(int f, int x, int y, int id): f(f), x(x), y(y), id(id) {}
    bool operator < (const P &rhs) const {
        return x<rhs.x;
    }
}a[maxn], a1[maxn];

int n, m, mx, my, mm, nx;
int b[maxx], ans[maxn];

inline void max(int &x, int y) { if(x<y) x=y; }
inline void min(int &x, int y) { if(x>y) x=y; }
inline void clear(int x) { while(x<=mm) if(b[x]) b[x]=0, x+=x&-x; else return; }
inline void update(int x, int d) { while(x<=mm) max(b[x],d), x+=x&-x; }
inline int query(int x) { int ans=0; while(x) max(ans,b[x]), x-=x&-x; return ans;}

void pre() {
    int mx=0, my=0; nx=0;
    for(int i=1; i<=n; ++i)
        if(a[i].f) max(mx,a[i].x), max(my,a[i].y);
    for(int i=1; i<=n; ++i)
        if(a[i].x<=mx&&a[i].y<=my) a[++nx]=a[i];
}

void solve(int l, int r) {
    if(l==r) return;
    int m=(l+r)/2;
    solve(l,m), solve(m+1,r);
    sort(a+l,a+m+1), sort(a+m+1,a+r+1);
    int j=l;
    for(int i=m+1; i<=r; ++i) {
        if(!a[i].f) continue;
        while(j<=m&&a[j].x<=a[i].x) {
            if(!a[j].f) update(a[j].y,a[j].x+a[j].y);
            ++j;
        }
        int tmp=query(a[i].y);
        if(tmp) min(ans[a[i].id],a[i].x+a[i].y-tmp);
    }
    while(--j>=l) if(!a[j].f) clear(a[j].y);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read();
    for(int i=1; i<=n; ++i) {
        int x=read()+1, y=read()+1;
        max(mx,x), max(my,y);
        a1[i]=P(0,x,y,i);
    }
    while(m--) {
        int f=read()-1, x=read()+1, y=read()+1;
        max(mx,x), max(my,y);
        ++n, a1[n]=P(f,x,y,n);
    }
    ++mx, ++my, mm=mx+my;

    for(int i=1; i<=n; ++i) a[i]=a1[i], ans[i]=1e9;
    pre(); solve(1,nx);
    for(int i=1; i<=n; ++i) a[i]=a1[i], a[i].x=mx-a[i].x;
    pre(); solve(1,nx);
    for(int i=1; i<=n; ++i) a[i]=a1[i], a[i].y=my-a[i].y;
    pre(); solve(1,nx);
    for(int i=1; i<=n; ++i) a[i]=a1[i], a[i].x=mx-a[i].x, a[i].y=my-a[i].y;
    pre(); solve(1,nx);

    for(int i=1; i<=n; ++i) if(a1[i].f) printf("%d\n", ans[i]);
}