「2025 杭电多校 1」1002. 夜世界

    「2025 杭电多校 1」1002. 夜世界

    HDU 7980

    有 nn 座金矿排成一行,每座金矿有一个属性 aia_i,表示该金矿一天产出的金币数量。每座金矿都潜伏着一只有属性 bib_i 的哥布林,代表该哥布林的贪婪值。

    每天夜晚都会发生以下的事件:你将从第 11 座金矿走到第 nn 座金矿,初始金币为 00,每走过一座金矿 ii,以下两件事情依次发生:

    • 你将获得 aia_i 金币。
    • 哥布林向你索要 bib_i 金币,若你没有 bib_i 金币则需要将所有金币交给哥布林。

    你需要在这里 mm 天,每天都会进行以下操作中的一种:

    • 1 x y:令 ax=ya_x = y,修改是持久的。
    • 2 x y:令 bx=yb_x = y,修改是持久的。
    • 3 x:版本回到第 xx 天。
    • 4 k p1 p2 ... pk:有 kk 个位于金矿 p1,p2,…,pkp_1, p_2, \dots, p_k 的哥布林向你索要金币的方式变为“若你目前拥有 ss 金币,它们将要向你索要 ⌈s2⌉\left\lceil \frac{s}{2} \right\rceil 金币”,变化是临时的。你需要求出当晚要交给哥布林多少金币。

    数据范围:1≤n,m≤2×1051\leq n, m \leq 2\times 10^5,0≤k≤2×1050 \leq k \leq 2\times 10^5,0≤ai,bi≤1090 \leq a_i, b_i \leq 10^9。

    时空限制:33s / 256256MiB。

    Solution

    本题最重要的是考虑如何从第 11 座金矿走到第 nn 座金矿。

    最直观的想法是,初始的金币增大的情况下,最终留下的金币一定不会变少。设初始金币为 xx,经过一个金矿区间 [l,r][l, r] 后最终留下来的金币个数为 f(x)f(x),猜想 f(x)f(x) 是一个仅有两段的分段函数,第一段是斜率为 00 的直线,第二段是斜率为 11 的直线,形如 “_/”。

    考虑使用两个参数 a,ba, b 来刻画 f(x)f(x),其中 a,ba, b 分别表示分段点,以及第一段的高度,可以得知 f(x)=b+max⁡(0,x−a)f(x) = b + \max(0, x - a)。

    现在考虑先经过函数 f1(x)=b1+max⁡(0,x−a1)f_1(x) = b_1 + \max(0, x - a_1) 后经过函数 f2(x)=b2+max⁡(0,x−a2)f_2(x) = b_2 + \max(0, x - a_2) 时,如何合并得到函数 f(x)=b+max⁡(0,x−a)f(x) = b + \max(0, x - a),简单画图分析得

    • 若 b1≥a2b_1 \geq a_2,则 a=a1,b=b2+b1−a2a = a_1, b = b_2 + b_1 - a_2。
    • 若 b1<a2b_1 < a_2,则 a=a1+a2−b1,b=b2a = a_1 + a_2 - b_1, b = b_2。

    由于合并操作可以进行,我们可以归纳证明 f(x)f(x) 的确是形如 “_/” 的分段函数。

    维护函数就只需要使用线段树简单维护即可,不过多赘述。

    历史版本回溯可以无脑使用主席树。或者离线建出一个类似 git 的版本树:每次遇到一个新版本时,就从当前节点下面新建一个叶子节点,边权即为修改的信息,并将当前节点指向该叶子节点;每次版本回溯时,就将当前节点指向历史节点。最后从上到下遍历一遍,统计每个版本的询问即可。

    时间复杂度 O(mlog⁡n)\mathcal{O}(m \log n)。

    #include <bits/stdc++.h>
    
    using s64 = long long;
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int N = 200100;
    
    int n, m;
    s64 a[N], b[N];
    
    struct Info {
        s64 a, b;
    
        Info() { a = b = 0; }
        Info(s64 _a, s64 _b) : a(_a), b(_b) {}
    
        s64 value(s64 x) {
            return b + std::max(0LL, x - a);
        }
    };
    
    Info create(s64 a, s64 b) {
        if (a <= b) {
            return Info(b - a, 0);
        } else {
            return Info(0, a - b);
        }
    }
    
    Info operator + (const Info &lhs, const Info &rhs) { // 队长写的 (:
        if(lhs.b<=rhs.a)return {lhs.a+rhs.a-lhs.b,rhs.b};
        return {lhs.a,rhs.b+lhs.b-rhs.a};
    }
    
    int root[N];
    namespace SGT {
        const int pond = 5001000;
    
        int NodeCount;
        struct node {
            int lc, rc;
            Info info;
            s64 a, b;
        } t[pond];
    
        void upd(int p) {
            t[p].info = t[t[p].lc].info + t[t[p].rc].info;
            t[p].a = t[t[p].lc].a + t[t[p].rc].a;
        }
    
        void init() {
            NodeCount = 0;
        }
    
        void build(int &p, int l, int r) {
            p = ++ NodeCount, t[p].lc = t[p].rc = 0;
            if (l == r) {
                t[p].a = a[l], t[p].b = b[l];
                t[p].info = create(t[p].a, t[p].b);
                return;
            }
            int mid = (l + r) >> 1;
            build(t[p].lc, l, mid), build(t[p].rc, mid + 1, r);
            upd(p);
        }
    
        void insert(int &p, int q, int l, int r, int x, int type, int y) {
            p = ++ NodeCount, t[p] = t[q];
            if (l == r) {
                if (type == 1) {
                    t[p].a = y;
                } else {
                    t[p].b = y;
                }
                t[p].info = create(t[p].a, t[p].b);
                return;
            }
            int mid = (l + r) >> 1;
            if (x <= mid) {
                insert(t[p].lc, t[q].lc, l, mid, x, type, y);
            } else {
                insert(t[p].rc, t[q].rc, mid + 1, r, x, type, y);
            }
            upd(p);
        }
    
        Info ask(int p, int l, int r, int s, int e) {
            if (s <= l && r <= e) {
                return t[p].info;
            }
            int mid = (l + r) >> 1;
            if (s <= mid && mid < e) {
                return ask(t[p].lc, l, mid, s, e) + ask(t[p].rc, mid + 1, r, s, e);
            }
            if (s <= mid) {
                return ask(t[p].lc, l, mid, s, e);
            } else {
                return ask(t[p].rc, mid + 1, r, s, e);
            }
        }
    
        s64 geta(int p, int l, int r, int x) {
            if (l == r) {
                return t[p].a;
            }
            int mid = (l + r) >> 1;
            if (x <= mid) {
                return geta(t[p].lc, l, mid, x);
            } else {
                return geta(t[p].rc, mid + 1, r, x);
            }
        }
    }
    
    void work() {
        std::cin >> n >> m;
    
        for (int i = 1; i <= n; i ++) {
            std::cin >> a[i];
        }
        for (int i = 1; i <= n; i ++) {
            std::cin >> b[i];
        }
    
        SGT::init();
        SGT::build(root[0], 1, n);
    
        for (int i = 1; i <= m; i ++) {
            root[i] = root[i - 1];
    
            int opt, x, y, k;
            std::cin >> opt;
    
            if (opt == 1) {
                std::cin >> x >> y;
                SGT::insert(root[i], root[i], 1, n, x, 1, y);
            } else if (opt == 2) {
                std::cin >> x >> y;
                SGT::insert(root[i], root[i], 1, n, x, 2, y);
            } else if (opt == 3) {
                std::cin >> x;
                root[i] = root[x];
            } else {
                std::cin >> k;
    
                std::vector<int> pos;
    
                pos.push_back(0);
    
                for (int j = 1; j <= k; j ++) {
                    std::cin >> x;
                    pos.push_back(x);
                }
    
                pos.push_back(n + 1);
    
                s64 suma = SGT::t[root[i]].a;
                s64 x = 0;
                for (int j = 1; j < pos.size(); j ++) {
                    int p1 = pos[j - 1], p2 = pos[j];
    
                    Info res;
                    if (p1 + 1 == p2) {
                        res = Info(0, 0);
                    } else {
                        res = SGT::ask(root[i], 1, n, p1 + 1, p2 - 1);
                    }
    
                    x = res.value(x);
    
                    if (p2 > n) {
                        continue;
                    }
    
                    x += SGT::geta(root[i], 1, n, p2);
                    x = x / 2;
                }
    
                std::cout << (suma - x) << '\n';
            }
        }
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
        
        while (T --) {
            work();
        }
    
        return 0;
    }