ABC 221

Sat, Jan 24, 2026

https://atcoder.jp/contests/abc221

A. Seismic magnitude scales

https://atcoder.jp/contests/abc221/tasks/abc221_a

B. typo

https://atcoder.jp/contests/abc221/tasks/abc221_b

C. Select Mul

https://atcoder.jp/contests/abc221/tasks/abc221_c

D. Online games

https://atcoder.jp/contests/abc221/tasks/abc221_d

E. LEQ

https://atcoder.jp/contests/abc221/tasks/abc221_e

2026/1/24 segment tree の問題だとわかった状態だったが解説 AC

https://kenkoooo.com/atcoder/#/contest/show/76c42792-10db-491b-9486-ffc7f4f226e1?activeTab=Standings

$A_i \leq A_j$, $i < j$ を満たす $(i, j)$ について、間にある $j-i-1$ 個の要素それぞれに対して使う使わないの2通りがあるから端を $A_i$, $A_j$ とする部分列の個数は $2^{j-i-1}$ 通りである。

$r$ を固定したとき $A_l \leq A_r$ を満たす部分列の個数は

\begin{align*} \sum_{l \text{ s.t } A_l \leq A_r \wedge l<r} \frac{2^r}{2^{l+1}} = 2^{r} \sum_{l \text{ s.t } A_l \leq A_r \wedge l<r} \frac{1}{2^{l+1}} \end{align*}

である。よって左から順に見ていき、BIT の $A_i$ の index のところに $2^{-(i+1)}$ を加算しておけば、各 $r$ について上記の和を $O(\log N)$ で求めることができる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll A(N);
    rep(i, N) {
        cin >> A[i];
        A[i]--;
    }

    {
        vll v = A;
        sort(all(v));
        v.erase(unique(all(v)), v.end());
        map<ll, ll> mp;
        rep(i, (ll)v.size()) mp[v[i]] = i;
        rep(i, N) {
            A[i] = mp[A[i]];
        }
    }

    fenwick_tree<mint> fw(N);
    mint ans = 0;
    mint two = 1;
    rep(i, N) {
        ans += two * fw.sum(0, A[i] + 1);
        two *= 2;
        fw.add(A[i], two.inv());
    }
    cout << ans.val() << endl;
}