AtCoder ABC 150 C問題 "Count Order" 解法メモ

自分＆なかなか解けなくてほかの方の提出を見ても分からない方用の解法メモです。
こちらのnoteを拝見させていただいて初めて解けました。とても感謝しています。

#コード

#include <bits/stdc++.h>

typedef long long ll;
const int INF = 1e9;

using namespace std; 

#define REP(inc, bgn, end) for (int inc = bgn; inc < end; inc++)

int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n), a(n);
    REP(i, 0, n) cin >> p[i];
    REP(i, 0, n) cin >> q[i];

    /* 
    next_permutation()のための順列を作ります。
    この順列は、辞書順で一番小さいものです。
    */
    REP(i, 0, n) a[i] = i + 1;
    
    /* 
    連想配列に作った順列を格納ていきます。
    構造は以下のようになっています。
    Key: value = [順列]: 辞書順で数えたときの番号
    例) [1, 2, 3]: 1
     */
    map<vector<int>, int> mp;
    
    do {
        mp[a] = mp.size();
    } while (next_permutation(a.begin(), a.end()));

    int ans = abs(mp[p] - mp[q]);
    cout << ans << endl;
}

##next_permutationについて

※全ての順列を取得する場合は、関数に最初に与える範囲が昇順にソート済みになっている必要がある

と上記のnoteに書かれているように、next_permutationに渡す配列はソートされたものにしましょう。
コードの配列aはそのために作ったものです。

mp[a] = mp.size();

この部分ついて
配列aはnext_permutationによって毎回変わるイメージです。
mp.size()は連想配列の大きさを返しますが、do-while文によってmpの要素が増えるたびに1, 2, 3 ...と大きくなっていきます。
つまり、mp.size()はその順列（配列）が辞書順で何番目かを取得してくれています。