(6.9 Hard) Kattis - 2017 ICPC Mid-Atlantic Regional Contest - Avoiding Airports

原题链接：https://open.kattis.com/problems/avoidingairports

Avoiding Airports

题目描述

有$n$个国家，国家间有$m$条航班，第$i$个航班可以从国家$a_i$飞到$b_i$，起飞时间为$s_i$，到达时间为$e_i$，David当前在国家$1$，当前时间为$0$，David想要去国家$n$，他不在乎旅行一共要花多少时间，但是他特别讨厌在机场等待，如果他在起飞前等待了$t$时间，则它会获得$t^2$单位失望值，帮他找到一条失望值最小的路线。

输入

行	输入值	含义	范围
1	$n\ m$	国家数量 航班数量	$1\le n,m \le 200,000$
$2...m+1$	$a_i\ b_i\ s_i\ e_i$	起点 终点 起飞时间 到达时间	$1\le a_i,b_i \le n,0 \le s_i,e_i \le 10^6$

航班的起点和终点可能相同；不同航班间的起飞时间不同，到达时间也不同，也就是说，没有航班会有相同的起飞时间或者到达时间；输入保证David总是能够到达他的目的地。

输出

单独一行：最小失望值

示例输入1

5 8
1 2 1 10
2 4 11 16
2 1 9 12
3 5 28 100
1 2 3 8
4 3 20 21
1 3 13 27
3 5 23 24

示例输出1

12

说明

示例1最优路线为：

航班	起点	终点	起飞时间	到达时间	累计失望值
5	1	2	3	8	9
3	2	1	9	12	10
7	1	3	13	27	11
8	3	5	28	100	12

示例输入2

3 5
1 1 10 20
1 2 30 40
1 2 50 60
1 2 70 80
2 3 90 95

示例输出2

1900

解决方案

由于航班间的起飞时间和到达时间都不相同，我们将起飞时间从小到大排序并遍历，记当前时间为$s_i$，当前时间的最小失望值为$dp[s_i]$，由于每趟航班的起飞时间不同，因此当前时间的航班只有一趟，当前时间的航班为$i$，则$dp[s_i]=min_{e_j\le s_i,b_j==a_i}(dp[e_j]+(s_i-e_j)^2)$，即$dp[s_i]$等于在$s_i$时刻之前达到$a_i/b_j$的所有航班$j$中，$dp[e_j]+(s_i-e_j)^2$的最小值，这个状态转移可以通过凸包技巧Convex Hull Trick优化到$O(log(m))$，这里我们为每一个国家维护一个CHT(凸包直线集合)，我们先将当前计算出来的$dp[s_i]$按照$e_i$的大小插入一个优先级队列，在计算下一个$dp[s_i]$的时候，将优先级队列中到达时间小于等于$s_i$的值插入到对应国家的CHT中

时间复杂度

$O(m*log(m))$

代码

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

template<typename T>
struct Line {
    T k, b;
    // 集合中的直线按照斜率从小到大排序，该值表示本直线与下一条直线的交点的横坐标
    mutable T intersect_x;
    bool operator<(const Line<T>& o) const { return k < o.k; }  // 用于按照斜率排序
    bool operator<(T x) const { // 用于在Query时进行二分查找
        return intersect_x < x;
    }                                                  // 用于二分查找
    T Eval(T x) const { return k * x + b; }  // 求直线在x点的y值
    T IntersectX(const Line<T>& line) const { // 求与直线line的交点的横坐标
        assert(k != line.k); // 斜率不能相等，否则除0异常
        return Div(line.b - b, k - line.k);
    }
    T Div(T a, T b) const {
        if constexpr (std::is_integral<T>::value) {
            // floored division,
            // 因为两条直线之间的交点可能是小数，但是x是整数，因此小数部分永远不会取到
            // 所以求直线交点时只需要记录<=交点横坐标值的最大整数即可
            // 3/2 -> 1; -3/2 -> -2; 4/2 -> 2; -4/2 -> 2
            return a / b - ((a ^ b) < 0 && a % b);
        } else {
            return a / b;
        }
    }
};

// IS_SORTED=1表示插入和查询是按照斜率排好序的顺序进行的，n条直线的时间复杂度为O(n)
// IS_SORTED=0表示插入和查询默认是无序的，内部使用multiset排序，n条直线的时间复杂度为O(n*logn)
template <typename T, int IS_SORTED = 0, int FIND_MIN = 0>
class LineContainer {
   public:
    void Add(T k, T b) {
        if (FIND_MIN) Add(Line<T>{-k, -b, 0});
        else Add(Line<T>{k, b, 0});
    }
    // 查找使得k*x+b最大的那条直线并返回最大的k*x+b
    T Query(T x) {
        assert(!lines.empty());
        auto it = lines.begin();
        auto l = lines.lower_bound(x);
        return FIND_MIN ? -(l->Eval(x)) : l->Eval(x);
    }
    size_t Size() {
        return lines.size();
    }
    void Swap(LineContainer<T, IS_SORTED, FIND_MIN>& other) {
        lines.swap(other.lines);
    }
    void Merge(const LineContainer<T, IS_SORTED, FIND_MIN>& other) {
        for (auto line : other.lines) {
            Add(line);
        }
    }
   private:
    void Add(const Line<T>& line) {
        auto nxt = lines.insert(line), cur = nxt++, prev = cur;
        // 判断插入的直线后面的直线是否需要删除，如果删除则重新求相邻直线的交点
        while (Intersect(cur, nxt)) nxt = lines.erase(nxt);
        // 判断插入的直线本身是否需要删除，删除的话重新求相邻直线的交点
        if (prev != lines.begin() && Intersect(--prev, cur))
            Intersect(prev, cur = lines.erase(cur));
        // 判断插入的直线前面的那一条直线是否需要删除，删除的话重新求相邻直线的交点
        while ((cur = prev) != lines.begin() &&
               (--prev)->intersect_x >= cur->intersect_x)
            Intersect(prev, lines.erase(cur));
    }
    // 求直线l1与l2的交点横坐标（向下取整），并判断是否需要删除直线l2
    bool Intersect(typename multiset<Line<T>>::iterator l1, typename multiset<Line<T> >::iterator l2) {
        if (l2 == lines.end()) {
            l1->intersect_x = numeric_limits<T>::max();
            return false;
        }
        if (l1->k == l2->k) {
            l1->intersect_x = l1->b > l2->b ? numeric_limits<T>::max()
                                            : numeric_limits<T>::lowest();
        } else {
            l1->intersect_x = l1->IntersectX(*l2);
        }
        return l1->intersect_x >= l2->intersect_x;
    }

    multiset<Line<T>, less<>> lines;
};

template <typename T, int FIND_MIN>
class LineContainer<T, 1, FIND_MIN> {
   public:
    void Add(T k, T b) {
        if (FIND_MIN) Add(Line<T>{-k, -b, 0});
        else Add(Line<T>{k, b, 0});
    }
    // 查找使得k*x+b最大的那条直线并返回最大的k*x+b
    T Query(T x) {
        assert(!lines.empty());
        T ans;
        if (first_query) {
            first_query_x = x;
            first_query = false;
            ans = lines[0].Eval(x);
            for (int i = 1; i < lines.size(); ++i) {
                ans = max(lines[i].Eval(x), ans);
            }
        } else {
            // if x == first_query_x, we can not judge whether queries are ascend or descend
            assert(x != first_query_x);
            if (x > first_query_x) {
                while (lines.size() >= 2 && lines[0].Eval(x) <= lines[1].Eval(x)) {
                    lines.pop_front();
                }
                ans = lines.front().Eval(x);
            } else { //if (x < first_query_x) {
                while (lines.size() >= 2 && lines[lines.size() - 1].Eval(x) <= lines[lines.size() - 2].Eval(x)) {
                    lines.pop_back();
                }
                ans = lines.back().Eval(x);
            }
        }
        return FIND_MIN ? -ans : ans;
    }
    size_t Size() {
        return lines.size();
    }
    void Swap(LineContainer<T, 1, FIND_MIN>& other) {
        lines.swap(other.lines);
    }

   private:
    void Add(const Line<T>& line) {
        if (lines.empty()) lines.emplace_back(line);
        else {
            if (line.k <= lines[0].k) {
                if (line.k == lines[0].k) {
                    if (line.b > lines[0].b) lines.pop_front();
                    else return;
                }
                while (lines.size() >= 2 && lines[0].IntersectX(line) >= lines[0].IntersectX(lines[1])) {
                    lines.pop_front();
                }
                lines.emplace_front(line);
            } else {
                if (line.k == lines.back().k) {
                    if (line.b > lines.back().b) lines.pop_back();
                    else return;
                }
                while (lines.size() >= 2 && lines[lines.size()-1].IntersectX(line) <= lines[lines.size()-1].IntersectX(lines[lines.size()-2])) {
                    lines.pop_back();
                }
                lines.emplace_back(line);
            }
        }
    }

    deque<Line<T>> lines;
    bool first_query = true;
    T first_query_x;
};

class Solution {
    struct Edge {
        int u,v,s,e;
        bool operator<(const Edge& edge) const {
            return s < edge.s;
        }
        friend istream &operator>>(istream &is, Edge &r) {
          return is >> r.u >> r.v >> r.s >> r.e;
        }
        friend ostream &operator<<(ostream &os, const Edge &r) { 
            return os << "[" << r.u << ", " << r.v << ", " << r.s << ", " << r.e << "]";
        }
    };
public:
    void Solve() {
        // dp[ei] = min(dp[ej] + (si - ej)^2) ej <= si
        // frustration_i = min(frustracion_j + ej^2 - 2*ej*si) + si^2
        int n, m;
        while(cin>>n>>m) {
            vector<Edge> edges(m); cin>>edges;
            sort(all(edges));
            dbg(edges);

            ll ans = numeric_limits<ll>::max();
            if (n==1) ans = 0;
            vector<LineContainer<ll, 0, 1>> lines(n+1);
            priority_queue<tuple<int,int,ll>, vector<tuple<int,int,ll>>, greater<>> q;
            lines[1].Add(0, 0);
            rep(i,0,sz(edges)) {
                while(!q.empty() && get<0>(q.top()) <= edges[i].s) {
                    auto item = q.top(); q.pop();
                    int e = get<0>(item);
                    int v = get<1>(item);
                    ll frustration = get<2>(item);
                    dbg(edges[i].s);
                    dbg(e);
                    lines[v].Add(-2 * e, frustration + ll(e) * e);
                }
                dbg("----");
                if (lines[edges[i].u].Size() > 0) {
                    ll frustration = lines[edges[i].u].Query(edges[i].s) + ll(edges[i].s) * edges[i].s;
                    // dbg(frustration);
                    q.push(make_tuple(edges[i].e, edges[i].v, frustration));
                    if (edges[i].v == n) {
                        ans = min(ans, frustration);
                        // dbg(ans);
                    }
                }
            }
            cout << ans << endl;

            // cout << fixed << setprecision(9) << ans << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
    set_io("input");
    Solution().Solve();

    return 0;
}