题解 P7564 【[JOISC 2021 Day3] ボディーガード】

· · 题解

题意

有 n 个顾客在逛街，街视为一个数轴，每个顾客在 t_i 时刻从 a_i 位置开始逛街，以 1 单位每秒的速度走到 b_i 位置之后离开。如果 a_i<b_i 表示他向正方向走，否则表示他向负方向走。同时每个人有权值 c_i 表示单位时间内的工资数量。

一个保镖保护一个人需要跟一个人一起逛街（即相同时刻在相同位置），跟着 i 逛街 x 个单位时间获得 c_i\times x 的工资。保镖的移动速度不超过 1 单位每秒，保护一个人逛街的起止时间均不需要是一个整数。一个保镖在同一时刻只能保护一个人。

有 q 个保镖，第 x 个保镖在 P_x 时刻上岗，初始位置时 X_x，你需要求出每个保镖能够获得的小费最多是多少。

数据范围：n\le 2800,q\le 3\times 10^6,1\le t_i,a_i,b_i,c_i,P_i,X_i\le 10^9,a_i\ne b_i,c_i 为偶数。

solution

首先转化问题，把时间和位置作为两维，在坐标系中画出所有逛街的人的图像，即起点为 (t_i,a_i) ，终点为 (t+|a_i-b_i|,b_i) 的一个线段。那么一个保镖在坐标系上起点是 (p_i,x_i)，每个时刻只能向右上或者右下走，保镖的路径的图像与顾客的图像的重叠部分的长度就表示保护的时长。这样线段长度变成了原来的 \sqrt{2} 倍。

现在所有的线段都是与直线 y=x 平行或垂直的，不是很好处理，把坐标系顺时针旋转 45^\circ ，即一个点 (x,y) 变为 (x-y,x+y)。线段长度再 \times \sqrt{2}，现在的线段长度是原来的 2 倍，那么如果保镖与顾客的图像重叠的长度为 len，那么得到的工资是 len\times \frac{c_i}{2}。这就是 c_i 是偶数的作用。

注意到 n 很小，把所有顾客的线段的端点作为关键点，离散化，这样变成了一个 O(n)\times O(n) 的网格图，共 O(n^2) 个格点。可以 O(n^2) 地预处理出如果一个保镖走到了一个格点，之后他的最大收益 val_{i,j} 是多少。转移枚举下一步往上走还是右走，走的时候选覆盖这个线段的 c_i 最大的顾客保护。

现在剩下的问题就是走到格点之前的部分，一个保镖的策略是：要么一直往上走，找到一个合适的横着的线段，跟着走一段，到达格点；要么一直往右走，找到一个合适的竖着的线段，跟着走一段，到达格点。跟着走一段，然后获得格点的贡献是一个一次函数 kx+b 的形式，k 是 \frac{c_i}{2}，x 是保护的距离，b 是格点的贡献。一个保镖能走到的横着的线段和竖着的线段是一段前缀，把询问离线下来李超树维护即可。

具体的，枚举是往上走还是往右走，以往上走为例。找出初始位置在两个格线 i 和 i+1 之间的所有保镖，他们选择的格点一定是 val_{i+1,x}。然后按照纵坐标从大到小的顺序，把一次函数插入进去即可。每个保镖 j 询问一个前缀的一次函数中，x=X_{i+1}-P_j 时的最大值。

时间复杂度是 O((n^2+q)\log q)。空间复杂度 O(n^2+q)。

#include <bits/stdc++.h>
using namespace std;
namespace iobuff{//输入输出量较大，输入输出优化
    const int LEN=1000000;
    char in[LEN+5],out[LEN+5];
    char *pin=in,*pout=out,*ed=in,*eout=out+LEN;
    inline char gc(void){
        return pin==ed&&(ed=(pin=in)+fread(in,1,LEN,stdin),ed==in)?EOF:*pin++;
    }
    inline void pc(char c){
        pout==eout&&(fwrite(out,1,LEN,stdout),pout=out);
        (*pout++)=c;
    }
    inline void flush(){fwrite(out,1,pout-out,stdout),pout=out;}
    template<typename T> inline void read(T &x){
        static int f;
        static char c;
        c=gc(),f=1,x=0;
        while(c<'0'||c>'9') f=(c=='-'?-1:1),c=gc();
        while(c>='0'&&c<='9') x=10*x+c-'0',c=gc();
        x*=f;
    }
    template<typename T> inline void putint(T x,char div='\n'){
        static char s[20];
        static int top;
        top=0;
        x<0?pc('-'),x=-x:0;
        while(x) s[top++]=x%10,x/=10;
        !top?pc('0'),0:0;
        while(top--) pc(s[top]+'0');
        pc(div);
    }
}
using namespace iobuff;
const int N=5605,Q=3e6+5;
#define ll long long
#define int ll
#define y1 Yy1
#define y2 Yy2 
template<int T> struct lsh{//离散化
    int buc[T],tot;
    inline void ins(int x){buc[++tot]=x;}
    inline void build(){
        sort(buc+1,buc+1+tot);
        tot=unique(buc+1,buc+1+tot)-buc-1;
    }
    inline int operator ()(int x){return lower_bound(buc+1,buc+1+tot,x)-buc;}
    inline int operator [](int x){return buc[x];}
};
lsh<N> bx,by;
lsh<Q> qry;
int qx[Q],qy[Q];
namespace SGT{//李超树
    #define lid (id<<1)
    #define rid (id<<1|1)
    #define mid ((l+r)>>1)
    int k[Q<<2];ll b[Q<<2];
    void build(int id,int l,int r){
        k[id]=0;b[id]=-1;
        if(l==r)return;
        build(lid,l,mid);build(rid,mid+1,r);
    }
    inline ll calc(int id,int x){return 1ll*k[id]*x+b[id];}
    inline ll calc(int _k,ll _b,int x){return 1ll*_k*x+_b;}
    void insert(int id,int l,int r,int _k,ll _b){
        if(b[id]==-1){k[id]=_k;b[id]=_b;return;}
        if(calc(id,qry[mid])<calc(_k,_b,qry[mid]))swap(k[id],_k),swap(b[id],_b);
        if(l==r)return;
        if(calc(id,qry[r])<calc(_k,_b,qry[r]))insert(rid,mid+1,r,_k,_b);
        if(calc(id,qry[l])<calc(_k,_b,qry[l]))insert(lid,l,mid,_k,_b);
    }
    ll query(int id,int l,int r,int pos){
        if(b[id]==-1)return 0;
        if(l==r)return calc(id,qry[pos]);
        return max(calc(id,qry[pos]),pos<=mid?query(lid,l,mid,pos):query(rid,mid+1,r,pos));
    }
}
ll val[N][N];
int vx[N][N],vy[N][N];
template<typename T> inline void Max(T &a,T b){if(a<b)a=b;}
struct Line{
    int x1,x2,y1,y2,c;
    Line(int _x1=0,int _y1=0,int _x2=0,int _y2=0,int _c=0){x1=_x1;y1=_y1;x2=_x2;y2=_y2;c=_c;}
    inline void build(){
        x1=bx(x1);x2=bx(x2);y1=by(y1);y2=by(y2);
    }
}line[N];
vector<int> bucx[N],bucy[N];
int n,q;
void init(){
    bx.build();by.build();
    for(int i=1;i<=n;++i){
        line[i].build();//vx,vy 表示 (i,j) 向右走到 (i+1,j)/向上走到 (i,j+1) 的最大的 c
        if(line[i].x1==line[i].x2){
            for(int j=line[i].y1;j<line[i].y2;++j)
                Max(vy[line[i].x1][j],line[i].c);
        }else{
            for(int j=line[i].x1;j<line[i].x2;++j)
                Max(vx[j][line[i].y2],line[i].c);
        }
    }
    for(int i=bx.tot;i;--i)for(int j=by.tot;j;--j)
        val[i][j]=max(i<bx.tot?val[i+1][j]+1ll*vx[i][j]*(bx[i+1]-bx[i]):0ll,j<by.tot?val[i][j+1]+1ll*vy[i][j]*(by[j+1]-by[j]):0ll);
}
inline bool cmpx(int x,int y){return qx[x]>qx[y];}
inline bool cmpy(int x,int y){return qy[x]>qy[y];}
ll ans[Q];
signed main(){
    read(n);read(q);
    for(int i=1,a,b,t,c,x1,y1,x2,y2;i<=n;++i){
        read(t);read(a);read(b);read(c);
        x1=t;y1=a;
        x2=t+abs(a-b);y2=b;
        line[i]=Line(x1-y1,x1+y1,x2-y2,x2+y2,c>>1);
        bx.ins(x1-y1);bx.ins(x2-y2);
        by.ins(x1+y1);by.ins(x2+y2);
    }
    init();
    for(int i=1,t,a;i<=q;++i){
        read(t);read(a);
        qx[i]=t-a;qy[i]=t+a;
        bucx[bx(qx[i])].push_back(i);
        bucy[by(qy[i])].push_back(i);
    }
    for(int i=1;i<=bx.tot;++i){
        if(!bucx[i].size())continue;
        qry.tot=0;
        sort(bucx[i].begin(),bucx[i].end(),cmpy);
        for(int x:bucx[i])qry.ins(bx[i]-qx[x]);
        qry.build();
        int R=qry.tot;
        SGT::build(1,1,R);
        int flag=by.tot;
        for(int id:bucx[i]){
            while(flag&&by[flag]>=qy[id]){
                SGT::insert(1,1,R,vx[i-1][flag],val[i][flag]);
                --flag;
            }
            Max(ans[id],SGT::query(1,1,R,qry(bx[i]-qx[id])));
        }
    }
    for(int i=1;i<=by.tot;++i){
        if(!bucy[i].size())continue;
        qry.tot=0;
        sort(bucy[i].begin(),bucy[i].end(),cmpx);
        for(int x:bucy[i])qry.ins(by[i]-qy[x]);
        qry.build();
        int R=qry.tot;
        SGT::build(1,1,R);
        int flag=bx.tot;
        for(int id:bucy[i]){
            while(flag&&bx[flag]>=qx[id]){
                SGT::insert(1,1,R,vy[flag][i-1],val[flag][i]);
                --flag;
            }
            Max(ans[id],SGT::query(1,1,R,qry(by[i]-qy[id])));
        }
    }
    for(int i=1;i<=q;++i)putint(ans[i]);
    flush();
    return 0;
}