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

发表于 分类于 本文字数： 1.4k 阅读时长 ≈ 5 分钟

Description

Link：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, \cdots, p_k 的哥布林向你索要金币的方式变为“若你目前拥有 ss 金币，它们将要向你索要 ⌈s2⌉\left\lceil \frac{s}{2} \right\rceil 金币”，变化是临时的。你需要求出当晚要交给哥布林多少金币。

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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
#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;
}