题解：P9624 [ICPC2020 Nanjing R] Certain Scientific Railgun

__staring__ · 2025-01-19 10:22:39 · 题解

由于 x 轴与 y 轴的移动相互独立，所有移动路径总是可以拆分成如下形式：在 x 轴上走了 [-a,b]，即往上最远走到了 b，往下最远走到了 -a，在 y 轴上走了 [-c,d]，即往右最远走到了 d，往左最远走到了 -c，其中 a,b,c,d \ge 0。

拆分后，路径的代价为 a+b+c+d+\min(a,b)+\min(c,d)，所求为所有代价的 \min，那么可以枚举 \min 的取向，此时路径的代价为 \min(2a+b+2c+d,2a+b+c+2d,a+2b+2c+d,a+2b+c+2d)。

如果所求式子带有 2a，可以将所有 x_i \le 0 的点横坐标翻倍，即 x_i \leftarrow 2x_i，2b,2c,2d 同理，将对应方向的点对应坐标翻倍。

现在所求为：找到 a,b,c,d \ge 0，使得每个点满足 x_i \in [-a,b] 或 y_i \in [-c,d]，且 a+b+c+d 最小。

注意到当 a,b 固定时，c,d 的取值也固定，可以对 a 进行扫描线，用数据结构维护 c,d 关于 b 的答案。

当 a-1 \rightarrow a 时，找到 x_i=a-1 的 \max y_i 和 \min y_i，全局对 c,d 进行 chkmax，即 c \leftarrow \max(c,-\min y_i),d \leftarrow \max(d,\max y_i)，可以用吉司机线段树处理。

但注意到，当 a=-\inf 时，c,d 关于 b 不升，因此 c,d 总是具有单调性，可以在线段树上二分，做区间覆盖

这里的代码实现比较暴力，读者可自行优化

#include<bits/stdc++.h>
using namespace std;
namespace staring
{
    typedef long long LL;
    typedef vector<int> VEC;
    typedef pair<int,int> PII;
    typedef pair<LL,LL> PLL;
    #define fir first
    #define sec second

    #define FOR(i,a,b) for(int i=(a),__i=(b);i<=__i;i++)
    #define ROF(i,a,b) for(int i=(a),__i=(b);i>=__i;i--)

    template<typename TYPE>
    TYPE gmax(TYPE &x,const TYPE y){return x<y?x=y:x;}
    template<typename TYPE>
    TYPE gmin(TYPE &x,const TYPE y){return y<x?x=y:x;}

    static constexpr int SIZE=1<<20;
    static char buffin[SIZE]{},*pin1{},*pin2{};
    static char buffout[SIZE]{},*pout{buffout};
    #define GETC() (pin1==pin2&&(pin2=(pin1=buffin)+fread(buffin,1,SIZE,stdin),pin1==pin2)?EOF:*pin1++)
    #define PUTC(c) (pout-buffout==SIZE&&(fwrite(buffout,1,SIZE,stdout),pout=buffout),*pout++=c)
    template<typename TYPE>
    void read(TYPE &x)
    {
        static int signf{0},chin{0};
        x=signf=0,chin=GETC();
        while(chin<'0'||chin>'9')signf|=chin=='-',chin=GETC();
        while(chin>='0'&&chin<='9')x=(x<<3)+(x<<1)+(chin^48),chin=GETC();
        if(signf)x=-x;
    }
    template<typename TYPE>
    void write(TYPE x,char ch=' ',bool f=0)
    {
        static char stack[64]{},top{0};
        !x&&PUTC('0'),x<0&&(x=-x,PUTC('-'));
        while(x)stack[top++]=x%10|48,x/=10;
        while(top)PUTC(stack[--top]);
        if(ch)PUTC(ch);
    }

}using namespace staring;

constexpr int N=1e5+5,M=N<<2;

PII p[N];
LL lsh[N],mny[N],mxy[N];
LL sufc[N],sufd[N];
LL c[M],d[M],b[M];
LL cdb[M],cb[M],db[M];
LL maxc[M],maxd[M];
LL tagc[M],tagd[M];

#define lp (p<<1)
#define rp (p<<1|1)
#define mid (l+r>>1)

void pushup(int p)
{
    c[p]=min(c[lp],c[rp]);
    d[p]=min(d[lp],d[rp]);
    b[p]=min(b[lp],b[rp]);
    cb[p]=min(cb[lp],cb[rp]);
    db[p]=min(db[lp],db[rp]);
    cdb[p]=min(cdb[lp],cdb[rp]);
    maxc[p]=max(maxc[lp],maxc[rp]);
    maxd[p]=max(maxd[lp],maxd[rp]);
}

void cover(int p,LL vc,LL vd)
{
    if(vd)
    {
        d[p]=maxd[p]=tagd[p]=vd;
        db[p]=vd+b[p],cdb[p]=vd+cb[p];
    }
    if(vc)
    {
        c[p]=maxc[p]=tagc[p]=vc;
        cb[p]=vc+b[p],cdb[p]=vc+db[p];
    }
}

void pushdown(int p)
{
    cover(lp,tagc[p],tagd[p]);
    cover(rp,tagc[p],tagd[p]);
    tagc[p]=tagd[p]=0;
}

void build(int p,int l,int r)
{
    tagc[p]=tagd[p]=0;
    if(l==r)
    {
        c[p]=sufc[l],d[p]=sufd[l],b[p]=lsh[l];
        cb[p]=c[p]+b[p],db[p]=d[p]+b[p];
        cdb[p]=c[p]+d[p]+b[p];
        maxc[p]=c[p],maxd[p]=d[p];
    }
    else build(lp,l,mid),build(rp,mid+1,r),pushup(p);
}

void modifyC(LL v,int p,int l,int r)
{
    if(l==r)return cover(p,v>maxc[p]?v:0,0);
    pushdown(p);
    if(v>maxc[rp])cover(rp,v,0),modifyC(v,lp,l,mid);
    else modifyC(v,rp,mid+1,r);
    pushup(p);
}

void modifyD(LL v,int p,int l,int r)
{
    if(l==r)return cover(p,0,v>maxd[p]?v:0);
    pushdown(p);
    if(v>maxd[rp])cover(rp,0,v),modifyD(v,lp,l,mid);
    else modifyD(v,rp,mid+1,r);
    pushup(p);
}

LL calc(int zero,int tot)
{
    sufc[tot]=sufd[tot]=0;
    ROF(b,tot-1,zero)
    {
        sufc[b]=max(sufc[b+1],-mny[b+1]);
        sufd[b]=max(sufd[b+1],mxy[b+1]);
    }
    build(1,zero,tot);

    LL res=1e12;
    FOR(a,1,zero)
    {
        gmin(res,-lsh[a]+cdb[1]);
        modifyC(-mny[a],1,zero,tot);
        modifyD(mxy[a],1,zero,tot);
    }
    return res;
}

void solve()
{
    int n;read(n);
    FOR(i,1,n)read(p[i].fir),read(p[i].sec);
    p[++n]={0,0};

    int tot=0,zero=0;
    sort(p+1,p+n+1);
    FOR(i,1,n)
    {
        if(i==1||p[i].fir!=p[i-1].fir)
        {
            lsh[++tot]=p[i].fir,mny[tot]=p[i].sec;
            if(!p[i].fir)zero=tot;
        }
        mxy[tot]=p[i].sec;
    }

    LL res=1e12;

    FOR(i,1,zero)lsh[i]*=2;
    FOR(i,1,tot)(mny[i]<=0)&&(mny[i]*=2),(mxy[i]<=0)&&(mxy[i]*=2);
    gmin(res,calc(zero,tot));
    FOR(i,1,zero)lsh[i]/=2;
    FOR(i,1,tot)(mny[i]<=0)&&(mny[i]/=2),(mxy[i]<=0)&&(mxy[i]/=2);

    FOR(i,1,zero)lsh[i]*=2;
    FOR(i,1,tot)(mny[i]>=0)&&(mny[i]*=2),(mxy[i]>=0)&&(mxy[i]*=2);
    gmin(res,calc(zero,tot));
    FOR(i,1,zero)lsh[i]/=2;
    FOR(i,1,tot)(mny[i]>=0)&&(mny[i]/=2),(mxy[i]>=0)&&(mxy[i]/=2);

    FOR(i,zero,tot)lsh[i]*=2;
    FOR(i,1,tot)(mny[i]<=0)&&(mny[i]*=2),(mxy[i]<=0)&&(mxy[i]*=2);
    gmin(res,calc(zero,tot));
    FOR(i,zero,tot)lsh[i]/=2;
    FOR(i,1,tot)(mny[i]<=0)&&(mny[i]/=2),(mxy[i]<=0)&&(mxy[i]/=2);

    FOR(i,zero,tot)lsh[i]*=2;
    FOR(i,1,tot)(mny[i]>=0)&&(mny[i]*=2),(mxy[i]>=0)&&(mxy[i]*=2);
    gmin(res,calc(zero,tot));
    FOR(i,zero,tot)lsh[i]/=2;
    FOR(i,1,tot)(mny[i]>=0)&&(mny[i]/=2),(mxy[i]>=0)&&(mxy[i]/=2);

    write(res,'\n');
}

int main()
{
    int T;read(T);
    while(T--)solve();

    fwrite(buffout,1,pout-buffout,stdout);
    return 0;
}