营业额统计

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3576 字
给定数列，第i天的最小波动值=min|ai-
一本通
例
正文

/*
原题：T1565 「一本通 4.6 例 1」营业额统计（HNOI2002）
题意：给定数列，第 i 天的最小波动值 = min|ai-aj|（j<i），求所有天波动值之和（第一天即 a1）。
思路：用 Treap 维护已出现的值。每天读入 x，在树中找前驱(最大小于 x)与后继(最小大于 x)，
取绝对值差较小者累加；若树中已存在 x 则差为 0。随后插入 x。
复杂度：时间 O(n log n)，空间 O(n)。
易错点：第一天波动值就是 a1 本身；x 可能已在集合中（差为 0 要单独判断）；
答案可能超 int，用 long long。split/merge 用下标返回，避免 vector 重分配导致悬垂引用。
*/
#include <bits/stdc++.h>
using namespace std;
struct Treap {
    struct Node {
        int l, r, pri, cnt, sz;
        long long key;
    };
    vector<Node> t;
    int root;
    Treap(){
        t.push_back({0, 0, 0, 0, 0, 0});
        root = 0;
    }
    int rnd(){
        return rand();
    }
    int newNode(long long key){
        t.push_back({0, 0, rnd(), 1, 1, key});
        return (int)t.size() - 1;
    }
    void upd(int x){
        if(x) t[x].sz = t[t[x].l].sz + t[t[x].r].sz + t[x].cnt;
    }
    pair<int, int> split(int x, long long key){
        if(!x) return {0, 0};
        if(t[x].key < key){
            auto p = split(t[x].r, key);
            t[x].r = p.first;
            upd(x);
            return {x, p.second};
        }else{
            auto p = split(t[x].l, key);
            t[x].l = p.second;
            upd(x);
            return {p.first, x};
        }
    }
    int merge(int L, int R){
        if(!L || !R) return L | R;
        if(t[L].pri > t[R].pri){
            t[L].r = merge(t[L].r, R);
            upd(L);
            return L;
        }else{
            t[R].l = merge(L, t[R].l);
            upd(R);
            return R;
        }
    }
    void insert(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        auto p2 = split(R, key + 1);
        int M = p2.first, R2 = p2.second;
        if(M){
            t[M].cnt++;
            t[M].sz++;
        }else{
            M = newNode(key);
        }
        root = merge(merge(L, M), R2);
    }
    int kthIn(int x, int k){
        while(x){
            int ls = t[t[x].l].sz;
            if(k <= ls) x = t[x].l;
            else if(k <= ls + t[x].cnt) return (int)t[x].key;
            else {
                k -= ls + t[x].cnt;
                x = t[x].r;
            }
        }
        return -1;
    }
    long long pred(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        long long res = -1;
        if(t[L].sz) res = kthIn(L, t[L].sz);
        root = merge(L, R);
        return res;
    }
    long long succ(long long key){
        auto p = split(root, key + 1);
        int L = p.first, R = p.second;
        long long res = -1;
        if(t[R].sz) res = kthIn(R, 1);
        root = merge(L, R);
        return res;
    }
    bool contains(long long key){
        auto p = split(root, key);
        int L = p.first, R = p.second;
        auto p2 = split(R, key + 1);
        int M = p2.first, R2 = p2.second;
        bool ok = (M != 0 && t[M].cnt > 0);
        root = merge(merge(L, M), R2);
        return ok;
    }
    int size(){
        return t[root].sz;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    Treap tr;
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        long long x;
        cin >> x;
        if(tr.size() == 0){
            ans += x;
        }else{
            long long best = LLONG_MAX;
            long long p = tr.pred(x), s = tr.succ(x);
            if(p != -1) best = min(best, x - p);
            if(s != -1) best = min(best, s - x);
            if(tr.contains(x)) best = 0;
            ans += best;
        }
        tr.insert(x);
    }
    cout << ans << "\n";
    return 0;
}
营业额统计

正文

一本通·提高篇的其它内容
