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
| constexpr int Lim = 2e5 + 1;
constexpr int64_t Inf = 1e18;
struct SegTree {
int64_t tag, mn;
SegTree *lc, *rc;
};
SegTree *null = new SegTree;
SegTree *newTree() {
auto t = new SegTree;
t->lc = t->rc = null;
t->tag = 0;
t->mn = Inf;
return t;
}
void add(SegTree *t, int64_t v) {
t->tag += v;
t->mn += v;
}
void push(SegTree *t) {
if (t->lc != null) add(t->lc, t->tag);
if (t->rc != null) add(t->rc, t->tag);
t->tag = 0;
}
void pull(SegTree *t) { t->mn = std::min(t->lc->mn, t->rc->mn); }
void modify(SegTree *&t, int l, int r, int x, int64_t v) {
if (t == null) t = newTree();
if (r - l == 1) {
t->mn = v;
return;
}
int m = (l + r) / 2;
push(t);
if (x < m) modify(t->lc, l, m, x, v);
else modify(t->rc, m, r, x, v);
pull(t);
}
int64_t query(SegTree *t, int l, int r, int x) {
if (r - l == 1 || t == null) return t->mn;
int m = (l + r) / 2;
push(t);
if (x < m) return query(t->lc, l, m, x);
else return query(t->rc, m, r, x);
}
SegTree *merge(SegTree *t1, SegTree *t2) {
if (t1 == null) return t2;
if (t2 == null) return t1;
t1->mn = std::min(t1->mn, t2->mn);
push(t1);
push(t2);
t1->lc = merge(t1->lc, t2->lc);
t1->rc = merge(t1->rc, t2->rc);
return t1;
}
SegTree *solve(int s, int64_t v, int ban) {
SegTree *t = null;
modify(t, 0, Lim, s, v);
std::string opt;
while (std::cin >> opt) {
if (opt == "end") return t;
if (opt == "set") {
int y, v;
std::cin >> y >> v;
int64_t mn = t->mn;
add(t, v);
if (y != ban) modify(t, 0, Lim, y, mn);
} else {
int y;
std::cin >> y;
auto t1 = solve(y, query(t, 0, Lim, y), ban);
modify(t, 0, Lim, y, Inf);
t = merge(t, t1);
}
}
return t;
}
|