ABC190 F問題（Shift and Inversions）を解く

ABC（AtCoder Beginner Contest）190 のF問題をC++で解いてみました。セグメント木の演習です。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

F問題 Shift and Inversions（Difficulty : 1321）

問題はリンク先をご覧ください。

ABC190 F問題 Shift and Inversions

セグメント木を使って反転数を求めます。AtCoder Problems による Difficulty は 1321 でした。

解答案

セグメント木を使って反転数を求めることは、AOJ ALDS1 5_D で紹介していました。

値0からN-1までを重複なく持つ数列 a₀, a₁, …. a_N-1 に対して、以下の処理をします。

• 空のセグメント木を用意する。
• 要素 a₀ より大きい範囲にある数字を合計する。具体的には、[a₀+1, N) の合計を求める。初期値なので、この値は0である。
• 要素 a₀ を1にする。
• 次に要素 a₁ より大きい範囲にある数字を合計する。具体的には、[a₁+1, N) の合計を求める。 この値を変数 result に加える。
• 要素 a1 を1にする。
• ・・・
• これを a_N-1 まで繰り返すと、result に反転数が格納されている。

値をセグメント木の要素に格納して、何かの処理をするのは、ABC339E問題（解説）でも紹介しました。

C++ プログラム例（ABC190F）

問題の制約から反転数は32ビットに収まらないため、ACL にあるセグメント木クラス segtree を使います（自前ライブラリは、int固定で実装していました）。

最初の並びの反転数は、セグメント木を使って求めます（28－33行目）。

2行目以降の出力ですが、a[i] が最後に移動することにより、以下の計算をします。

• a[i] より大きい、n-1-a[i] 個の反転数が増えます。
• a[i] の後ろにある 0 から a[i]-1 までの a[i] 個の反転数が減ります。

以下が、C＋＋プログラムとなります。

#include <bits/stdc++.h>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

typedef long long int ll;

ll op(ll a, ll b)
{
	return a + b;
}

ll e(void)
{
	return 0LL;
}

int main()
{
	int n;
	cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	ll result = 0;
	segtree<ll, op, e> st(n + 1);
	for (int i = 0; i < n; ++i) {
		result += st.prod(a[i] + 1, n);
		st.set(a[i], 1);
	}

	cout << result << endl;
	for (int i = 1; i < n; ++i) {
		result += n - 1 - a[i - 1];
		result -= a[i - 1];
		cout << result << endl;
	}

	return 0;
}

どちらも AC（Accepted＝正しいプログラム）と判定されました。

最後に

セグメント木の演習を増やすために記事を書きました。セグメント木についての記事は、タグから検索できます。

引き続き ABC の問題を紹介していきます。