KokiYamaguchi https://blog.hatena.ne.jp/KokiYamaguchi/ Learning Algorithms https://kokiymgch.hatenablog.com/ まず数列 $a$ の転倒数を求める問題を考えますより正確には $i a_j$ となるようなものの数を求める問題で，これは fenwick tree などのデータ構造を使って以下のように解けます fenwick_tree<long long> ft(MAX); long long ans = 0; rep(i, n) { ans += ft.sum(a[i] + 1, MAX); ft.add(a[i], 1); } まず今見ている値を不等式の右辺の値として計算結果に加算して，次に今後その値が不等式の左辺としてどれくらい結果に寄与するかというのを考えているだけですところで上記を踏まえると，一般に… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkokiymgch.hatenablog.com%2Fentry%2F2020%2F11%2F03%2F143606" title="数列上の数の組み合わせであって不等式を満たすものの数を数える - Learning Algorithms" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-11-03 14:36:06 rich https://kokiymgch.hatenablog.com/entry/2020/11/03/143606 1.0 100%