势能，但仅限于势能吗？
需要知道线段树并非万能，很多看起来兼容的操作其实是不兼容的。举例：
区间取 min, max、区间查询 min, max
发现在涉及最值操作的时候，把区间元素值看作分段函数和取最值的性质是比较贴的。
那么相当于把所有大于 / 小于 \(v\) 的部分推平。查询是好做的。区间加、区间查询 min, max
相当于竖直方向平移。区间加等差数列、区间查询 min, max
发现是和另一个固定的一次函数做线性加；发现是不可做的。区间取 min、区间求和
也即把所有大于 / 小于 \(v\) 的部分推平，还要求点值之和。
看起来不可做，因为求和没办法用这样的语言体系简单阐释，只能考虑脱离这个语言体系，真的去找到这样的凸起。这样看起来是特别慢的。
但实际上最后一条是可做的，吉如一发明了一种特定的方法，并证明了在仅有区间取 min / max + 区间求和操作时，复杂度是 \(O(q\log n)\) 的；如果再增加其他任何区间操作，复杂度是 \(O(q\log^2 n)\) 的。
区间取 min / 区间求和
记录最大值 \(mx\)、次大值 \(se\)、最大值出现次数 \(cnt\)。当 \(v\in(se,mx)\) 时，发现只有 \(mx\) 需要被更新。此时 \(s\gets s-(mx-v)\cdot cnt\)。
否则，\(se\) 也需要被更新，暴力递归直到满足上一条后停止。复杂度 \(O(q\log n)\)。
#include <bits/stdc++.h>
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
struct {
long long s;
int l, r, mx, se, d, cnt;
} t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
int a[maxn];
void pushup(int p) {
if (t[lt].mx == t[rt].mx) {
t[p].mx = t[lt].mx, t[p].cnt = t[lt].cnt + t[rt].cnt;
t[p].se = std::max(t[lt].se, t[rt].se);
}
else if (t[lt].mx > t[rt].mx) {
t[p].mx = t[lt].mx, t[p].cnt = t[lt].cnt;
t[p].se = std::max(t[lt].se, t[rt].mx);
}
else {
t[p].mx = t[rt].mx, t[p].cnt = t[rt].cnt;
t[p].se = std::max(t[lt].mx, t[rt].se);
}
t[p].s = t[lt].s + t[rt].s;
return;
}
void bld(int p, int l, int r) {
t[p].d = inf;
t[p].l = l, t[p].r = r;
if (l == r) {
t[p].s = t[p].mx = a[l], t[p].cnt = 1, t[p].se = 0;
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
pushup(p);
return;
}
void pushval(int p, int v) {
if (v <= t[p].mx) {
t[p].s -= (long long)(t[p].mx - v) * t[p].cnt;
t[p].mx = t[p].d = v;
}
return;
}
void pushdown(int p) {
if (t[p].d != inf) {
pushval(lt, t[p].d), pushval(rt, t[p].d);
t[p].d = inf;
}
return;
}
void add(int p, int l, int r, int v) {
if (t[p].mx <= v)
return;
if (l <= t[p].l && t[p].r <= r && v > t[p].se) {
pushval(p, v);
return;
}
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
add(lt, l, r, v);
if (r > mid)
add(rt, l, r, v);
pushup(p);
return;
}
int askmx(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].mx;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1, res = 0;
if (l <= mid)
res = askmx(lt, l, r);
if (r > mid)
res = std::max(res, askmx(rt, l, r));
return res;
}
long long asks(int p, int l, int r) {
if (l <= t[p].l && t[p].r <= r)
return t[p].s;
pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
auto res = 0ll;
if (l <= mid)
res = asks(lt, l, r);
if (r > mid)
res += asks(rt, l, r);
return res;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
bld(1, 1, n);
for (int op, l, r; m--; ) {
std::cin >> op >> l >> r;
if (op == 0) {
int v;
std::cin >> v;
add(1, l, r, v);
}
else if (op == 1)
std::cout << askmx(1, l, r) << '\n';
else
std::cout << asks(1, l, r) << '\n';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}区间取 min、区间操作、区间求和
例：最假女选手
可以用相似的方法来维护；