転倒数 [第四回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202010-open/tasks/past202010_k

解説

https://atcoder.jp/contests/past202010-open/submissions/21472875

差分計算を頑張ろう。
差分だけを計算することで計算量を抑えてACするという問題が一定数ある。
今回の問題も各クエリでの連結事に連結によって増加する答えの量を計算していく。
数学的帰納法的に説明していこう。

1番目のクエリについて

これは数列xが最初の数列になる。
そして、これに対する今回要求されている答えを普通に計算すればいい。
これをいかにやるかも少しテクニックが要求される。
今回要求されている答えは実は有名問題であり、転倒数と呼ばれる。
これはバブルソートをする場合の回数のことでもあり、これを計算するにはBITを使った解法がある。
詳しいやり方はググるといいだろう。
この部分は転倒数の知識を問う問題。

k番目のクエリまでカウントが完了しているときにk+1番目のクエリの数列を加える場合

まず自明な所としてk+1番目として加えようとしている数列内部での転倒数は答えに加えられる。

次に、これまでの数列と加えようとしている数列の間で転倒数として増加する個数は何通りあるだろうか。
例えば、1と2による転倒数の増加を考えてみると、[これまでに存在する1の個数]*[追加しようとしている2の個数]となる。
ここで制約でひときわ目を引くaij≦20が役に立つ。
数の種類数は20までしかないので、このようなとある2つの数間での転倒数の増加をすべてのパターンで全探索して計算が可能である。
よって、すべての数のパターンについて転倒数を計算して足し合わせれば、既にある数列と追加しようとする数列間での転倒数も計算できる。

あとは？

これを後は実装する。
各数列の転倒数と、数が何個あるかは事前に計算しておく。
あとは答えの差分計算と、既にある数列にある数が何個含まれるかを更新して実装を頑張る。
modライブラリも必要だな。
積と和くらいなのでライブラリが無くても何とかなるが、作っておくとバグらず安心。

int K, Q;
vector<int> A[101010];
mint tot[101010];
mint cnt[101010][21];
mint cnt2[21];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K;
    rep(k, 0, K) {
        int n; cin >> n;
        rep(i, 0, n) {
            int x; cin >> x;
            A[k].push_back(x);
            cnt[k][A[k][i]] += 1;
        }
        tot[k] = BubbleSortCount(A[k]);
    }

    cin >> Q;
    mint ans = 0;
    rep(_, 0, Q) {
        int b; cin >> b; b--;
        ans += tot[b];
        rep(x, 1, 21) rep(y, x + 1, 21) ans += mint(cnt2[y]) * mint(cnt[b][x]);
        rep(x, 1, 21) cnt2[x] += cnt[b][x];
    }
    cout << ans << endl;
}