本题卡常...

Problem

Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。

我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 (xmy) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 (x,y) ，那么她离近的天使玩偶可能埋下的地方有多远。

因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为 dist(A,B)=|Ax-Bx|+|Ay-By|。其中 Ax 表示点 A 的横坐标，其余类似。

Solution

题解很妙啊
我一开始是想搞四个函数
而题解直接把每个点对称一下
然后对时间设维，这样就免去了排序
以及复制数组什么的

一开始开了 O2 仍旧 T 飞
我就把代码里的inplace_merge给替换掉了
A 了...
这告诉我们归并时不要偷懒（

然而不开 O2 还是 T 飞
（我就是不想做常数优化怎样）

Code

// Code by ajcxsu
// Problem: angel toys

#include<bits/stdc++.h>
using namespace std;

inline void gn(int &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=6e5+10, M=1e6+10;
struct Node {
    int x, y, k;
    int id;
} a[N], p[N], cac[N];
bool operator < (const Node &x, const Node &y) {
    return x.x<y.x;
}
inline int mmin(const int &x, const int &y) { return x<y?x:y; }
inline int mmax(const int &x, const int &y) { return x>y?x:y; }
int ans[N], idx;

#define lowbit(x) x&-x
int C[M];
int stk[N], t;
inline void updata(int x, int d, bool force=false) {
    if(!force) stk[++t]=x;
    while(x<M) {
        C[x]=force?d:mmax(C[x], d);
        x+=lowbit(x);
    }
}
inline int query(int x) {
    int ret=-0x3f3f3f3f;
    while(x) {
        ret=mmax(C[x], ret);
        x-=lowbit(x);
    }
    return ret;
}
inline void clear() {
    while(t) updata(stk[t--], -0x3f3f3f3f, true);
}

inline void merge(int l, int r) {
    if(l==r) return;
    int mid=(l+r)>>1, i=l, j=mid+1, k=l;
    merge(l, mid), merge(mid+1, r);
    while(i<=mid && j<=r) {
        if(p[i].x<=p[j].x) {
            if(p[i].k<=1) updata(p[i].y, p[i].x+p[i].y);
            cac[k++]=p[i++];
        }
        else {
            if(p[j].k>1) ans[p[j].id]=mmin(ans[p[j].id], p[j].x+p[j].y-query(p[j].y));
            cac[k++]=p[j++];
        }
    }
    while(i<=mid) cac[k++]=p[i++];
    while(j<=r) {
        if(p[j].k>1) ans[p[j].id]=mmin(ans[p[j].id], p[j].x+p[j].y-query(p[j].y));
        cac[k++]=p[j++];
    }
    clear();
    for(int i=l;i<=r;i++) p[i]=cac[i];
}

int main() {
    memset(C, -0x3f, sizeof(C));
    memset(ans, 0x3f, sizeof(ans));
    int n,m;
    gn(n), gn(m);
    int x,y,k,lx,ly;
    lx=ly=0;
    for(int i=1;i<=n;i++) {
        gn(x), gn(y);
        x++, y++;
        a[i]={x,y};
        lx=mmax(lx, x), ly=mmax(ly, y);
    }
    for(int i=1+n;i<=m+n;i++) {
        gn(k), gn(x), gn(y);
        x++, y++;
        lx=mmax(lx, x), ly=mmax(ly, y);
        a[i]={x,y,k};
        if(a[i].k>1) a[i].id=++idx;
    }
    lx++, ly++;
    n+=m;
    memcpy(p, a, sizeof(Node)*(n+1)), merge(1, n);
    memcpy(p, a, sizeof(Node)*(n+1));
    for(int i=1;i<=n;i++)
        p[i].x=lx-p[i].x;
    merge(1,n);
    memcpy(p, a, sizeof(Node)*(n+1));
    for(int i=1;i<=n;i++)
        p[i].y=ly-p[i].y;
    merge(1,n);
    memcpy(p, a, sizeof(Node)*(n+1));
    for(int i=1;i<=n;i++)
        p[i].x=lx-p[i].x, p[i].y=ly-p[i].y;
    merge(1,n);
    for(int i=1;i<=idx;i++) printf("%d\n", ans[i]);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4169.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆