/
beats_summax_chmin.hpp
87 lines (79 loc) · 2.46 KB
/
beats_summax_chmin.hpp
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
#include "ds/segtree/segtree_beats.hpp"
template <typename T>
struct Beats_SumMax_Chmin {
struct SumMax {
struct X {
T sum, max, maxc, max2;
bool fail;
};
using value_type = X;
static X op(const X& x, const X& y) {
if (x.max == -infty<T>) return y;
if (y.max == -infty<T>) return x;
X z;
z.sum = x.sum + y.sum;
z.max = max(x.max, y.max);
z.maxc = (x.max == z.max ? x.maxc : 0) + (y.max == z.max ? y.maxc : 0);
z.max2 = -infty<T>;
if (z.max > x.max && x.max > z.max2) z.max2 = x.max;
if (z.max > x.max2 && x.max2 > z.max2) z.max2 = x.max2;
if (z.max > y.max && y.max > z.max2) z.max2 = y.max;
if (z.max > y.max2 && y.max2 > z.max2) z.max2 = y.max2;
z.fail = 0;
return z;
}
static constexpr X unit() { return {0, -infty<T>, 0, -infty<T>, 0}; }
bool commute = true;
};
struct AddChmin {
using X = pair<T, T>;
using value_type = X;
static constexpr X op(const X& x, const X& y) {
auto [a, b] = x;
auto [d, e] = y;
a += d, b += d, b = min(b, e);
return {a, b};
}
static constexpr X unit() { return {0, infty<T>}; }
bool commute = false;
};
struct Beats {
using Monoid_X = SumMax;
using Monoid_A = AddChmin;
using X = typename Monoid_X::value_type;
using A = typename Monoid_A::value_type;
static X act(X& x, const A& a, int cnt) {
assert(!x.fail);
if (x.max == -infty<T>) return x;
auto [add, mi] = a;
x.sum += cnt * add, x.max += add, x.max2 += add;
if (mi == infty<T>) return x;
T before_max = x.max;
x.max = min(x.max, mi);
if (x.maxc == cnt) { x.max2 = x.max, x.sum = cnt * x.max; }
elif (x.max2 < x.max) { x.sum += (x.max - before_max) * x.maxc; }
else {
x.fail = 1;
}
return x;
}
};
using X = typename SumMax::X;
SegTree_Beats<Beats> seg;
Beats_SumMax_Chmin(vc<T>& A) {
seg.build(len(A), [&](int i) -> X { return from_element(A[i]); });
}
template <typename F>
Beats_SumMax_Chmin(int n, F f) {
seg.build(n, [&](int i) -> X { return from_element(f(i)); });
}
void set(int i, T x) { seg.set(i, from_element(x)); }
// (sum, max)
pair<T, T> prod(int l, int r) {
auto e = seg.prod(l, r);
return {e.sum, e.max};
}
static X from_element(T x) { return {x, x, 1, x}; }
void chmin(int l, int r, ll x) { seg.apply(l, r, {0, x}); }
void add(int l, int r, ll x) { seg.apply(l, r, {x, infty<T>}); }
};