提出 #72233857

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <functional>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define sz(x) (int)(x).size()
using namespace std;

template<typename Node>
struct SegTree {
    int n, lg, size;
    Node e; // 항등원
    vector<Node> tree;
    function<Node(Node, Node)> func;
    int log2(int n) {
        int res = 0;
        while (n > (1 << res)) res++;
        return res;
    }
    SegTree(int n, const Node& e, auto func) : n(n), lg(log2(n)), size(1<<lg), e(e), tree(size<<1, e), func(func) {}
    SegTree(const vector<Node>& v, const Node& e, auto func) : n(sz(v)), lg(log2(n)), size(1<<lg), e(e), tree(size<<1, e), func(func) {
        for (int i = 0; i < n; i++) {
            tree[i+size] = v[i];
        }
        for (int i = size-1; i > 0; i--) {
            tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
        }
    }
    void add(int i, const Node& val) {
        tree[--i |= size] += val;
        while (i >>= 1) {
            tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
        }
    }
    void update(int i, const Node& val) {
        tree[--i |= size] = val;
        while (i >>= 1) {
            tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
        }
    }
    Node query(int i) {
        return tree[--i | size];
    }
    Node query(int l, int r) {
        Node L = e, R = e;
        for (--l |= size, --r |= size; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) L = func(L, tree[l++]);
            if (~r & 1) R = func(tree[r--], R);
        }
        return func(L, R);
    }
    int find_kth(Node k) {
        int node = 1, st = 1, en = size;
        while (st != en) {
            int mid = (st + en) / 2;
            node <<= 1;
            if (tree[node] >= k) {
                en = mid;
            }
            else {
                k -= tree[node];
                node |= 1; st = mid+1;
            }
        }
        return st;
    }
};

typedef long long ll;
const ll MOD = 998244353;

int main() {
    fastio; int N; cin >> N;
    vector<int> v(N);
    for (auto& i : v) cin >> i;
    vector<int> L(N), R(N);
    SegTree<int> sg(N+1, 0, [](int a, int b) { return a+b; });
    for (int i = 0; i < N; i++) {
        L[i] = sg.query(1, v[i]-1);
        R[i] = v[i]-1-L[i];
        sg.add(v[i], 1);
    }
    ll c = 1, t = 0;
    for (int i = 1; i < N; i++) {
        t += (c * (ll)R[i]); t %= MOD;
        c = (c*2) % MOD;
    }
    ll ans = 0;
    for (int i = 0; i < N-1; i++) {
        ans += (ll)L[i]*R[i]; ans %= MOD;
        ans += L[i]*t; ans %= MOD;
        t = (t - R[i+1] + MOD) % MOD;
        t *= (MOD+1)/2; t %= MOD;
    }
    cout << ans << "\n";
    return 0;
}

提出情報

ジャッジ結果