小清新动态开点线段树优化 dp 题。
首先题目中的 if 嵌套看起来就很烦，可以考虑建树，外面再套一层大的 if 0 ... end，这样就将本题转化成一个树上问题。
考虑树形 dp。设 \(f_{u,i}\) 表示 从结点 \(u\) 出来时，\(x\) 的值是 \(i\) 的最少花费。
不难转移：
- 对于
set命令：
\(\begin{cases} f_{u,y} \gets \min\limits_{i}{f_{u,i}} \\ f_{u,i} \gets f_{u,i} + v & i \neq y \end{cases}\)
- 对于
if命令：
\(\begin{cases} f_{u,y} \gets f_{u,y} + f_{v,y} \\ f_{u,i} \gets \min(f_{u,i}, f_{u,y} + f_{v,i}) & i \neq y \end{cases}\)
注意转移时 dp 值都是同时计算。
直接暴力转移显然是 \(O(n^2)\) 的，但是我们发现对于每个结点 \(u\)，真正有用的状态只有 \(u\) 子树内 \(y\) 的取值。可以考虑对每个结点开一个动态开点线段树，存 \(u\) 的所有状态。转移时只需单点修改、整体加和单点查询，对于 if 命令大力线段树合并即可。时间复杂度 \(O(n \log n)\)。
map + 启发式合并的做法看不懂，我太菜了。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int N = 200000;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
int rt[maxn], n, m, stk[maxn], top, tot;
// int head[maxn], len;
vector<int> G[maxn];
struct node {
int x, v, op;
node(int a = 0, int b = 0, int c = 0) : x(a), v(b), op(c) {}
} a[maxn];
// struct edge {
// int to, next;
// } edges[maxn];
//
// void add_edge(int u, int v) {
// edges[++len].to = v;
// edges[len].next = head[u];
// head[u] = len;
// }
namespace SGT {
ll tree[maxn * 30], tag[maxn * 30];
int ntot, ls[maxn * 30], rs[maxn * 30];
void clear() {
ntot = 0;
mems(tree, 0x3f);
mems(tag, 0);
mems(ls, 0);
mems(rs, 0);
}
void pushup(int x) {
tree[x] = min(tree[ls[x]], tree[rs[x]]);
}
void pushdown(int x) {
if (!tag[x]) {
return;
}
if (ls[x]) {
tree[ls[x]] += tag[x];
tag[ls[x]] += tag[x];
}
if (rs[x]) {
tree[rs[x]] += tag[x];
tag[rs[x]] += tag[x];
}
tag[x] = 0;
}
void updpos(int &rt, int l, int r, int x, ll y) {
if (!rt) {
rt = ++ntot;
}
// printf("upd: %d %d %d %d %lld\n", rt, l, r, x, y);
if (l == r) {
tree[rt] = y;
return;
}
pushdown(rt);
int mid = (l + r) >> 1;
if (x <= mid) {
updpos(ls[rt], l, mid, x, y);
} else {
updpos(rs[rt], mid + 1, r, x, y);
}
pushup(rt);
}
void update(int rt, ll x) {
tree[rt] += x;
tag[rt] += x;
}
ll query(int rt, int l, int r, int x) {
// printf("%d %d %d %d\n", rt, l, r, x);
if (!rt) {
return inf;
}
if (l == r) {
return tree[rt];
}
pushdown(rt);
int mid = (l + r) >> 1;
if (x <= mid) {
return query(ls[rt], l, mid, x);
} else {
return query(rs[rt], mid + 1, r, x);
}
}
int merge(int u, int v, int l, int r) {
if (!u || !v) {
return u | v;
}
if (l == r) {
tree[u] = min(tree[u], tree[v]);
return u;
}
pushdown(u);
pushdown(v);
int mid = (l + r) >> 1;
ls[u] = merge(ls[u], ls[v], l, mid);
rs[u] = merge(rs[u], rs[v], mid + 1, r);
pushup(u);
return u;
}
}
void dfs(int u) {
SGT::updpos(rt[u], 0, N, a[u].x, 0);
for (int v : G[u]) {
if (a[v].op == 1) {
ll tmp = SGT::tree[rt[u]];
SGT::update(rt[u], a[v].v);
if (a[v].x != m) {
SGT::updpos(rt[u], 0, N, a[v].x, tmp);
}
} else {
ll tmp = SGT::query(rt[u], 0, N, a[v].x);
if (tmp < inf) {
dfs(v);
SGT::update(rt[v], tmp);
SGT::updpos(rt[u], 0, N, a[v].x, inf);
rt[u] = SGT::merge(rt[u], rt[v], 0, N);
}
}
}
}
void solve() {
SGT::clear();
scanf("%d%d", &n, &m);
stk[++top] = 0;
for (int i = 0; i < n; ++i) {
char op[9];
scanf("%s", op);
if (op[0] == 's') {
int x, y;
scanf("%d%d", &x, &y);
a[++tot] = node(x, y, 1);
G[stk[top]].pb(tot);
} else if (op[0] == 'i') {
int x;
scanf("%d", &x);
a[++tot] = node(x, 0, 2);
G[stk[top]].pb(tot);
stk[++top] = tot;
} else {
--top;
}
}
dfs(0);
printf("%lld\n", SGT::tree[rt[0]]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}