区间最值操作基础题，但是有点码农。
依然考虑势能线段树，维护区间和 \(\textrm{sum}\)、最大值 \(\textrm{M1}\)、次大值 \(\textrm{M2}\)、最大值个数 \(\textrm{Mcnt}\)、最小值 \(\textrm{m1}\)、次小值 \(\textrm{m2}\)、最小值个数 \(\textrm{mcnt}\)，另外需要区间加标记 \(\textrm{tags}\)、区间取最大值标记 \(\textrm{tagM}\)、区间取最小值标记 \(\textrm{tagm}\)。约定当区间只包含一个元素时，有 \(\textrm{M2}=-\infty,\textrm{m2}=+\infty\)，且初始情况下 \(\textrm{tagM}=-\infty,\textrm{tagm}=+\infty\)。
鉴于需要维护这么多信息和操作，本题的一个难点在于下传标记时的顺序需要正确实现。我的势能线段树的标记优先级为：区间加标记最优先，两种区间最值标记优先级相同。
在下传标记时，我们先下传区间加标记，同时对应地修改区间最值标记，再使用修改后的区间最值标记进行下传即可。由于势能线段树只会在仅有最大值/最小值发生变化时下传标记，因此这一部分容易实现。
可以证明时间复杂度为 \(O(n\log^2n)\)。
// Problem: P10639 BZOJ4695 最佳女选手
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10639
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x >= mod ? x - mod : x;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(unsigned int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
const ll N = 5e5 + 5, inf = 0x3f3f3f3f3f3f3f3fll;
ll n, m, a[N];
struct SegTree {
ll sum[N << 2], M1[N << 2], M2[N << 2], Mcnt[N << 2], m1[N << 2], m2[N << 2], mcnt[N << 2];
ll tagM[N << 2], tagm[N << 2], tags[N << 2];
#define lc(u) (u << 1)
#define rc(u) (u << 1 | 1)
void pushup(ll u) {
sum[u] = sum[lc(u)] + sum[rc(u)];
M1[u] = max(M1[lc(u)], M1[rc(u)]);
M2[u] = -inf;
if(M1[lc(u)] < M1[u]) chkmax(M2[u], M1[lc(u)]);
if(M2[lc(u)] < M1[u]) chkmax(M2[u], M2[lc(u)]);
if(M1[rc(u)] < M1[u]) chkmax(M2[u], M1[rc(u)]);
if(M2[rc(u)] < M1[u]) chkmax(M2[u], M2[rc(u)]);
Mcnt[u] = 0;;
if(M1[lc(u)] == M1[u]) Mcnt[u] += Mcnt[lc(u)];
if(M1[rc(u)] == M1[u]) Mcnt[u] += Mcnt[rc(u)];
m1[u] = min(m1[lc(u)], m1[rc(u)]);
m2[u] = +inf;
if(m1[lc(u)] > m1[u]) chkmin(m2[u], m1[lc(u)]);
if(m2[lc(u)] > m1[u]) chkmin(m2[u], m2[lc(u)]);
if(m1[rc(u)] > m1[u]) chkmin(m2[u], m1[rc(u)]);
if(m2[rc(u)] > m1[u]) chkmin(m2[u], m2[rc(u)]);
mcnt[u] = 0;;
if(m1[lc(u)] == m1[u]) mcnt[u] += mcnt[lc(u)];
if(m1[rc(u)] == m1[u]) mcnt[u] += mcnt[rc(u)];
}
void pushs(ll u, ll l, ll r, ll tag) {
sum[u] += tag * (r - l + 1);
if(M1[u] != -inf) M1[u] += tag;
if(M2[u] != -inf) M2[u] += tag;
if(m1[u] != +inf) m1[u] += tag;
if(m2[u] != +inf) m2[u] += tag;
tags[u] += tag;
if(tagM[u] != -inf) tagM[u] += tag;
if(tagm[u] != +inf) tagm[u] += tag;
}
void pushM(ll u, ll l, ll r, ll tag) {
if(m1[u] > tag) return;
sum[u] += (tag - m1[u]) * mcnt[u];
if(M2[u] == m1[u]) M2[u] = tag;
if(M1[u] == m1[u]) M1[u] = tag;
m1[u] = tag;
chkmax(tagM[u], tag);
chkmax(tagm[u], tag);
}
void pushm(ll u, ll l, ll r, ll tag) {
if(M1[u] < tag) return;
sum[u] += (tag - M1[u]) * Mcnt[u];
if(m2[u] == M1[u]) m2[u] = tag;
if(m1[u] == M1[u]) m1[u] = tag;
M1[u] = tag;
chkmin(tagM[u], tag);
chkmin(tagm[u], tag);
}
void pushdown(ll u, ll l, ll r) {
ll mid = (l + r) >> 1;
if(tags[u]) {
pushs(lc(u), l, mid, tags[u]);
pushs(rc(u), mid + 1, r, tags[u]);
tags[u] = 0;
}
if(tagM[u] != -inf) {
pushM(lc(u), l, mid, tagM[u]);
pushM(rc(u), mid + 1, r, tagM[u]);
tagM[u] = -inf;
}
if(tagm[u] != +inf) {
pushm(lc(u), l, mid, tagm[u]);
pushm(rc(u), mid + 1, r, tagm[u]);
tagm[u] = +inf;
}
}
void build(ll u, ll l, ll r) {
tags[u] = 0;
tagM[u] = -inf;
tagm[u] = +inf;
if(l == r) {
sum[u] = M1[u] = m1[u] = a[l];
M2[u] = -inf;
m2[u] = +inf;
Mcnt[u] = mcnt[u] = 1;
return;
}
ll mid = (l + r) >> 1;
build(lc(u), l, mid);
build(rc(u), mid + 1, r);
pushup(u);
}
void modifys(ll u, ll l, ll r, ll ql, ll qr, ll k) {
if(ql <= l && r <= qr) {
pushs(u, l, r, k);
return;
}
pushdown(u, l, r);
ll mid = (l + r) >> 1;
if(ql <= mid) modifys(lc(u), l, mid, ql, qr, k);
if(qr > mid) modifys(rc(u), mid + 1, r, ql, qr, k);
pushup(u);
}
void modifyM(ll u, ll l, ll r, ll ql, ll qr, ll k) {
if(m1[u] >= k) return;
if(ql <= l && r <= qr && m2[u] > k) {
pushM(u, l, r, k);
return;
}
pushdown(u, l, r);
ll mid = (l + r) >> 1;
if(ql <= mid) modifyM(lc(u), l, mid, ql, qr, k);
if(qr > mid) modifyM(rc(u), mid + 1, r, ql, qr, k);
pushup(u);
}
void modifym(ll u, ll l, ll r, ll ql, ll qr, ll k) {
if(M1[u] <= k) return;
if(ql <= l && r <= qr && M2[u] < k) {
pushm(u, l, r, k);
return;
}
pushdown(u, l, r);
ll mid = (l + r) >> 1;
if(ql <= mid) modifym(lc(u), l, mid, ql, qr, k);
if(qr > mid) modifym(rc(u), mid + 1, r, ql, qr, k);
pushup(u);
}
ll querys(ll u, ll l, ll r, ll ql, ll qr) {
if(ql <= l && r <= qr) return sum[u];
pushdown(u, l, r);
ll mid = (l + r) >> 1, ans = 0;
if(ql <= mid) ans += querys(lc(u), l, mid, ql, qr);
if(qr > mid) ans += querys(rc(u), mid + 1, r, ql, qr);
pushup(u);
return ans;
}
ll queryM(ll u, ll l, ll r, ll ql, ll qr) {
if(ql <= l && r <= qr) return M1[u];
pushdown(u, l, r);
ll mid = (l + r) >> 1, ans = -inf;
if(ql <= mid) chkmax(ans, queryM(lc(u), l, mid, ql, qr));
if(qr > mid) chkmax(ans, queryM(rc(u), mid + 1, r, ql, qr));
pushup(u);
return ans;
}
ll querym(ll u, ll l, ll r, ll ql, ll qr) {
if(ql <= l && r <= qr) return m1[u];
pushdown(u, l, r);
ll mid = (l + r) >> 1, ans = +inf;
if(ql <= mid) chkmin(ans, querym(lc(u), l, mid, ql, qr));
if(qr > mid) chkmin(ans, querym(rc(u), mid + 1, r, ql, qr));
pushup(u);
return ans;
}
#undef lc
#undef rc
}sgt;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i, 1, n) cin >> a[i];
sgt.build(1, 1, n);
for(cin >> m; m; --m) {
ll op;
cin >> op;
if(op == 1) {
ll l, r, x;
cin >> l >> r >> x;
sgt.modifys(1, 1, n, l, r, x);
}
else if(op == 2) {
ll l, r, x;
cin >> l >> r >> x;
sgt.modifyM(1, 1, n, l, r, x);
}
else if(op == 3) {
ll l, r, x;
cin >> l >> r >> x;
sgt.modifym(1, 1, n, l, r, x);
}
else if(op == 4) {
ll l, r;
cin >> l >> r;
cout << sgt.querys(1, 1, n, l, r) << endl;
}
else if(op == 5) {
ll l, r;
cin >> l >> r;
cout << sgt.queryM(1, 1, n, l, r) << endl;
}
else {
ll l, r;
cin >> l >> r;
cout << sgt.querym(1, 1, n, l, r) << endl;
}
}
return 0;
}