全区間転倒数

2 secs 1024 MB

shinnshinn

Problem

Submissions

Test cases

Editorial

解説

$i < j$ かつ $A_i > A_j$ となる１つのペアの解への寄与を考えます。

このペアが含まれる区間の個数は $i \times (N-j+1)$ 個です。

$j$ を固定して考えた際、 $A_i > A_j$ となる $i$ について、 $\sum i \times (N-j+1)$ が答えに加わることになります。

Fenwick treeで条件を満たす $A_i$ に $i$ を加算すれば $A_j$ が決まれば高速に総和を求めることができます。

実装

Rust

xxxxxxxxxx
 
use proconio::{marker::Usize1, *};
use ac_library::{FenwickTree, ModInt998244353};
​
type Mint = ModInt998244353;
​
fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
    }
​
    let mut tree = FenwickTree::new(n, Mint::new(0));
    let mut ans = Mint::new(0);
    for i in 0..n {
        ans += tree.sum(a[i]+1..) * (n-i);
        tree.add(a[i], Mint::new(i+1));
    }
​
    println!("{}", ans);
}

C++

xxxxxxxxxx
 
#include <bits/stdc++.h>
#include "atcoder/modint.hpp"
#include "atcoder/segtree.hpp"
using mint = atcoder::modint998244353;
using namespace std;
using ll = long long;
mint op(mint x, mint y) { return x + y;}
mint e() { return 0;}
int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    for (int i=0; i<n; i++) cin >> a[i];
    atcoder::segtree<mint, op, e> seg(n+1);
    mint ans = 0;
    for(int i=0; i<n; i++) {
        mint l = seg.prod(a[i]+1, n+1);
        ans += l * (n - i);
        seg.set(a[i], seg.get(a[i])+i+1);
    }
    cout << ans.val() << "\n";
}