(2859) CodeChef October Challenge 2015 - Jump mission/JUMP

原题链接：https://www.codechef.com/problems/JUMP

Jump mission

题目描述

有 $N$ 座山排成一排，每座山都有一个 $1 ∼ N$ 的唯一编号。第 $i$ 座山的索引为 $P_i$，高度为 $H_i$。大厨从第一座山出发，目标是到达第 $N$ 座山。而他唯一能做的，只有从一座山跳到右侧的一座山上（不允许向左跳）。从第 $i$ 座山跳到第 $j$ 座山上需要花费 $(H_i − H_j)^2$ 的能量。大厨处于第 $i$ 座山时，他必须为山上的居民们准备一道特别的菜，以答谢居民们让他使用他们的材料。做这道菜需要花费 $A_i$ 的能量（有些菜大厨特别喜欢做，做完之后神清气爽，所以 $A_i$ 可能为负）。为了增加难度，我们规定只有当满足 $i < j$ 且 $P_i < P_j$ 时，大厨才能从第 $i$ 座山跳到第 $j$ 座山。

请帮大厨选择一种“跳山”的方式，并使得他的能量花费最小。注意能量花费可以为负。

输入

行	输入值	含义	范围
1	$N$	山的数量	$2\le N \le 3*10^5$
2	$P_1\ P_2...P_N$	山的索引	$P$是$1～N$的排列，$P_1=1,P_N=N$
3	$A_1\ A_2...A_N$	做菜花费的能量	$-10^9\le A_i \le 10^9$
4	$H_1\ H_2...H_N$	山的高度	$1\le H_i \le 6*10^5$

输出

行	输出内容
1	最小能量花费

示例输入

5
1 4 3 2 5
0 1 3 0 0
1 2 3 4 5

示例输出

10

说明

最小能量消耗的跳法为1->4->5，花费为：$(H_4-H_1)^2+(H_5-H_4)^2+A_1+A_4+A_5=(4-1)^2+(5-4)^2+0+0+0=10$

解决方案

设第$i$座山峰的最小花费为$dp[i]$，容易得到$dp[i]=min_{j<i,P_j<P_i}(dp[j]+(H_i-H_j)^2+A_i)$，如果没有$P_j<P_i$这个限制，通过凸包技巧Convex Hull Trick，可以很容易将这个状态转移优化到$O(logN)$，但是有$P_j<P_i$这个限制，由于$P$是$1～N$的排列，数值的范围与$N$相同，因此我们可以通过线段树，在线段树上维护CHT(凸包直线集合)，每次计算出$dp[i]$时，我们将其更新到线段树$P_i$位置上的CHT中，而需要计算$dp[i]$时，我们查询线段树上$[0,P_i)$区间的CHT，初始的$dp[0]=A_0$。

时间复杂度

线段树查询某个区间的查询次数为$O(logN)$，而每次查询区间中的CHT的时间复杂度为$O(logN)$，一共查询$N$次，因此总的时间复杂度为：$O(N*log^2N)$

代码

#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; }
 
template <unsigned int MOD>
class ModInt {
public:
    ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
    explicit operator bool() const { return val != 0; }
    ModInt operator-() const { return ModInt() - *this; }
    ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); }
    ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); }
    ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); }
    ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
    ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
    ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
    ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
    ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
    // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; }
    unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; }
    bool operator==(const ModInt &r) const { return val == r.val; }
    bool operator!=(const ModInt &r) const { return val != r.val; }
    ModInt pow(long long n) const {
        ModInt x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv() const { return pow(MOD - 2); }
    unsigned int get_val() { return val; }
    friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; }
    friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
    unsigned int val;
    ModInt &set_v(unsigned int _v) {
        val = (_v < MOD) ? _v : _v - MOD;
        return *this;
    }
};
constexpr unsigned int mod = 1e9+7;
using Mint = ModInt<mod>;
 
#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
 
using Mint2 = ModInt<mod-1>;

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());
        if (lines.empty())
            return FIND_MIN ? numeric_limits<T>::max() : numeric_limits<T>::lowest();
        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 SegmentTree {
    struct Node{
        LineContainer<ll, 0, 1> lines;
    };
public:
    SegmentTree(int node_num) {
        offset_ = 1;
        while(offset_<node_num) offset_*=2;
        nodes.resize(offset_*2);
        // fill(nodes.begin(), nodes.end(), 0);
    }

    //将第k个值更新为a
    void Update(int k, ll slope, ll bias){
        //叶子节点
        k+=offset_-1;
        nodes[k].lines.Add(slope, bias);
        //向上更新
        while(k>0) {
            k = (k-1)/2;
            nodes[k].lines.Add(slope, bias);
        }
    }

    ll Query(int a,int b,int k, ll x) {
        return Query(a,b,k,0,offset_,x);
    }
private:
    //查询[a,b)区间的值
    //后面的参数是为了计算方便传入的
    //k是节点的编号，l,r表示这个节点代表区间[l,r)
    //外部调用时，使用query(a,b,0,0,n);
    ll Query(int a,int b,int k,int l,int r, ll x){
        //如果[a,b)和[l,r)不相交
        if(r<=a||b<=l) return numeric_limits<ll>::max();
        //如果[a,b)完全包含[l,r)，返回当前节点值
        if(a<=l && r<=b) return nodes[k].lines.Query(x);
        else{
            ll v1 = Query(a, b, k*2+1, l, (l+r)/2, x);
            ll v2 = Query(a, b, k*2+2, (l+r)/2, r, x);
            return min(v1, v2);
        }
    }
    int offset_;
    vector<Node> nodes;
};

class Solution {
public:
    void Solve() {
// j<i && pi < pj
// dp[i] = min(dp[j] + hj^2-2hj*hi)+hi^2+a[i]
// 5
//p 1 4 3 2 5
//a 0 1 3 0 0
//h 1 2 3 4 5
        int n;
        while(cin>>n) {
            vi p(n),a(n),h(n);
            cin>>p>>a>>h;

            ll ans = a[0];
            SegmentTree st(n);
            st.Update(p[0]-1, -2*h[0], ll(h[0])*h[0]+a[0]);
            rep(i,1,n) {
                ans = st.Query(0, p[i]-1, 0, h[i]) + ll(h[i])*h[i]+a[i];
                st.Update(p[i]-1, -2*h[i], ll(h[i])*h[i]+ans);
            }
            cout << ans << endl;

            // cout << fixed << setprecision(9) << ans << endl;
        }
    }
private:
};

void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO
    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;
}