2020-01-01から1年間の記事一覧
まず数列 $a$ の転倒数を求める問題を考えますより正確には $i a_j$ となるようなものの数を求める問題で,これは fenwick tree などのデータ構造を使って以下のように解けます fenwick_tree<long long> ft(MAX); long long ans = 0; rep(i, n) { ans += ft.sum(a[i] + </long>…
http://codeforces.com/contest/1437/problem/E の部分問題を考えます概要としては,ある整数列 $a$ が与えられ,「要素を一つ選び,任意の整数に置き換える」という操作を繰り返して $a$ を狭義単調増加な数列に変えるために必要な操作回数の最小値を求める…