gym103037 J - Bohemian Rhapsody

动态开点李超树，较基础的应用

---

题意

$n$ 个点，起点为 $1$ 终点为 $n$ ，共 $m$ 次航班，第 $i$ 次航班从 $a_i$ 飞往 $b_i$ ，从 $c_i$ 时间开始， $d_i$ 时间到达，初始时间为 $0$ ，若两次航班之间在机场等待了 $t$ 时间，则会增加 $t^2$ 的焦虑值，问能否从起点到达终点，若能最小化焦虑值。
其中 $1 \leq n, m \leq 2 \cdot 10^5, 1 \leq a_i, b_i \leq n, 0 \leq c_i, d_i \leq 10^9$ 。

思路

原以为是精妙的最短路但建不来图。
可以按航班的到达时间先后依次处理每一次航班，因为若先处理到达时间靠后的会遗漏到达时间靠前航班对之后的贡献。
先将所有航班按到达时间排序。假设排完序之后处理到了 $i$ 次航班，若要完成这趟航班从点 $a_i$ 到 $b_i$ 的转移，相当于需要在 $a_i$ 点中选择一趟航班 $j$ 使得 $d_j \leq c_i$ ，由 $j$ 向 $i$ 转移。记经过 $j$ 到达 $a_i$ 的最小焦虑为 $dp_j$ ，则选择 $j$ 航班之后乘坐 $i$ 航班会增加的焦虑为 $(c_i - d_j)^2$ ，则经 $j$ 由 $i$ 到达 $b_i$ 的焦虑为 $dp_j + (c_i - d_j)^2$ ，即为 $dp_j + c_i^2 + d_j^2 - 2 \cdot d_j \cdot c_i$ 。

$$dp_j + c_i^2 + d_j^2 - 2 \cdot d_j \cdot c_i$$

由于是做 $i$ 的转移，上式中 $c_i^2$ 可以看作定值忽略，式子转换为：

$$dp_j + d_j^2 - 2 \cdot d_j \cdot c_i$$

则完成 $i$ 的转移等价于在所有终点为 $a_i$ 且到达时间小于等于 $c_i$ 的航班中选择一个航班 $j$ 使得 $dp_j + d_j^2 - 2 \cdot d_j \cdot c_i$ 取值最小。
而上述式子的值可以看作一条直线 $f(x) = dp_j + d_j^2 - 2 \cdot d_j \cdot x$ 在 $x = c_i$ 处的取值，即之前所有航班的贡献皆可以等价为一条射线：

$$\begin{cases} k = -2 \cdot d_j\\ b = dp_j + d_j^2\\ x \geq d_j \end{cases}$$

那么我们现在需要做的是对于每一个点 $i \in [1, n]$ ，记录一个集合存放所有终点在 $i$ 点的航班对应的射线。
这么做之后上述航班 $i$ 的转移相当于在 $a_i$ 集合的若干条射线中查询 $x = c_i$ 处 $y$ 最小的射线对应的 $y$ 值。在完成航班 $i$ 的转移，计算出 $dp_i$ 后，还需要将 $i$ 对应的射线加入点 $b_i$ 的射线集合中。初态为 $dp[1] = 0$ ，初始时将直线 $y = 0$ 加入集合 $1$ 中即可。
上述操作是一个李超树经典应用，可以对每个点 $i \in [1, n]$ 建一棵动态开点李超树完成。
时空复杂度均为 $O(m \cdot log(10^9))$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-12-15 21:35:39
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const i64 INF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+5;
const int M=1e9+5;

struct Line{
    i64 k;
    i64 b;
    Line(){}
    Line(i64 _k,i64 _b){
        k=_k;
        b=_b;
    }
    i64 val(int x){
        return k*x+b;
    }
};
struct Seg_Tree{
    int tot;
    int rt[N];
    int lc[N<<5];
    int rc[N<<5];
    Line line[N<<5];
    int addnode(){
        tot++;
        lc[tot]=rc[tot]=0;
        line[tot]=Line(0,INF);
        return tot;
    }
    void insert(int &x,int l,int r,int ql,int qr,Line li){
        if(!x) x=addnode();
        int mid=l+r>>1;
        if(l>=ql&&r<=qr){
            if(li.val(l)<=line[x].val(l)&&li.val(r)<=line[x].val(r)){
                line[x]=li;
                return;
            }
            else if(li.val(l)>line[x].val(l)&&li.val(r)>line[x].val(r)) return;
            else{
                insert(lc[x],l,mid,ql,qr,li);
                insert(rc[x],mid+1,r,ql,qr,li);
            }
            return;
        }
        if(mid>=ql) insert(lc[x],l,mid,ql,qr,li);
        if(mid+1<=qr) insert(rc[x],mid+1,r,ql,qr,li);
    }
    void search(int x,int l,int r,int pos,i64 &res){
        if(!x) return;
        res=min(res,line[x].val(pos));
        if(l==r) return;
        int mid=l+r>>1;
        if(pos<=mid) search(lc[x],l,mid,pos,res);
        else search(rc[x],mid+1,r,pos,res);
    }
}tr;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,m;
    cin>>n>>m;

    vector<array<int,4>> edge(m,{0,0,0,0});
    for(auto &[a,b,c,d]:edge) cin>>a>>b>>c>>d;

    sort(edge.begin(),edge.end(),[&](const array<int,4> &x,const array<int,4> &y){
        if(x[3]!=y[3]) return x[3]<y[3];
        else return x[2]<y[2];
    });

    i64 ans=INF;
    tr.insert(tr.rt[1],0,M,0,M,Line(0,0));
    for(auto [a,b,c,d]:edge){
        i64 res=INF;
        tr.search(tr.rt[a],0,M,c,res);
        if(res==INF) continue;
        res+=1ll*c*c;
        if(b==n) ans=min(ans,res);
        else tr.insert(tr.rt[b],0,M,d,M,Line(-2ll*d,res+1ll*d*d));
    }

    if(ans==INF) cout<<"-1";
    else cout<<ans;

    return true&&false;
}