「2025 杭电多校 1」1002. 夜世界
有 n 座金矿排成一行,每座金矿有一个属性 a_i,表示该金矿一天产出的金币数量。每座金矿都潜伏着一只有属性 b_i 的哥布林,代表该哥布林的贪婪值。
每天夜晚都会发生以下的事件:你将从第 1 座金矿走到第 n 座金矿,初始金币为 0,每走过一座金矿 i,以下两件事情依次发生:
- 你将获得 a_i 金币。
- 哥布林向你索要 b_i 金币,若你没有 b_i 金币则需要将所有金币交给哥布林。
你需要在这里 m 天,每天都会进行以下操作中的一种:
1 x y:令 a_x = y,修改是持久的。2 x y:令 b_x = y,修改是持久的。3 x:版本回到第 x 天。4 k p1 p2 ... pk:有 k 个位于金矿 p_1, p_2, \dots, p_k 的哥布林向你索要金币的方式变为“若你目前拥有 s 金币,它们将要向你索要 \left\lceil \frac{s}{2} \right\rceil 金币”,变化是临时的。你需要求出当晚要交给哥布林多少金币。
数据范围:1\leq n, m \leq 2\times 10^5,0 \leq k \leq 2\times 10^5,0 \leq a_i, b_i \leq 10^9。
时空限制:3s / 256MiB。
Solution
本题最重要的是考虑如何从第 1 座金矿走到第 n 座金矿。
最直观的想法是,初始的金币增大的情况下,最终留下的金币一定不会变少。设初始金币为 x,经过一个金矿区间 [l, r] 后最终留下来的金币个数为 f(x),猜想 f(x) 是一个仅有两段的分段函数,第一段是斜率为 0 的直线,第二段是斜率为 1 的直线,形如 “_/”。
考虑使用两个参数 a, b 来刻画 f(x),其中 a, b 分别表示分段点,以及第一段的高度,可以得知 f(x) = b + \max(0, x - a)。
现在考虑先经过函数 f_1(x) = b_1 + \max(0, x - a_1) 后经过函数 f_2(x) = b_2 + \max(0, x - a_2) 时,如何合并得到函数 f(x) = b + \max(0, x - a),简单画图分析得
- 若 b_1 \geq a_2,则 a = a_1, b = b_2 + b_1 - a_2。
- 若 b_1 < a_2,则 a = a_1 + a_2 - b_1, b = b_2。
由于合并操作可以进行,我们可以归纳证明 f(x) 的确是形如 “_/” 的分段函数。
维护函数就只需要使用线段树简单维护即可,不过多赘述。
历史版本回溯可以无脑使用主席树。或者离线建出一个类似 git 的版本树:每次遇到一个新版本时,就从当前节点下面新建一个叶子节点,边权即为修改的信息,并将当前节点指向该叶子节点;每次版本回溯时,就将当前节点指向历史节点。最后从上到下遍历一遍,统计每个版本的询问即可。
时间复杂度 \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;
}