ABC 432
Table of Contents
https://atcoder.jp/contests/abc432
A. Permute to Maximize
https://atcoder.jp/contests/abc432/tasks/abc432_a
B. Permute to Minimize
https://atcoder.jp/contests/abc432/tasks/abc432_b
C. Candy Tribulation
https://atcoder.jp/contests/abc432/tasks/abc432_c
D. Suddenly, A Tempest
https://atcoder.jp/contests/abc432/tasks/abc432_d
E. Clamp
https://atcoder.jp/contests/abc432/tasks/abc432_e
2026/1/19 segment tree の問題であるということを知った状態で自力 AC
$l \geq r$ のとき
すべての要素が $l$ になるので答えは $l \times N$。
$l < r$ のとき
$f(x) = \max(l,\min(r,x))$ とすると、$x$ の値に応じて以下のようになる。
\begin{align} f(x) = \begin{cases} l & (x < l) \\ x & (l \leq x \leq r) \\ r & (x > r) \end{cases} \end{align}
よって $\sum_i \max(l,\min(r,A_i))$ は $(l \text{ 未満の } A_i \text{ の個数}) \times l + (l \leq A_i \leq r \text{ を満たす } A_i \text{ の和}) + (r \text{ 超過の } A_i \text{ の個数}) \times r$ と表せる。
これは $A_i$ の個数を管理する segment tree と $A$ の区間和を管理する segment tree を用いることで効率的に求めることができる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, Q;
cin >> N >> Q;
vll A(N);
rep(i, N) cin >> A[i];
ll m = (ll)5e5 + 5;
fenwick_tree<ll> fw(m);
for (auto a : A) fw.add(a, 1);
segtree<S, op, e> seg(m);
rep(i, m) seg.set(i, {i, 0});
rep(i, N) {
S now = seg.get(A[i]);
now.cnt++;
seg.set(A[i], now);
}
while (Q--) {
int t;
cin >> t;
if (t == 1) {
ll x, y;
cin >> x >> y;
x--;
fw.add(A[x], -1);
fw.add(y, 1);
{
S now = seg.get(A[x]);
now.cnt--;
seg.set(A[x], now);
}
{
S now = seg.get(y);
now.cnt++;
seg.set(y, now);
}
A[x] = y;
} else {
ll l, r;
cin >> l >> r;
ll ans = 0;
if (r <= l) {
ans += l * N;
} else {
ans += fw.sum(0, l) * l;
ans += fw.sum(r + 1, m) * r;
ans += seg.prod(l, r + 1).v;
}
cout << ans << endl;
}
}
}
F. Candy Redistribution
https://atcoder.jp/contests/abc432/tasks/abc432_f