\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

• Đầu tiên chúng ta quan tâm về phần sinh dãy hoán vị tiếp theo

Chúng ta thử sinh tất cả các hoán vị \(perm\) theo thứ tự tăng dần và bắt đầu xử lí khi nó trùng với hoán vị \(\pi\).

Dừng lại sau \(k\) bước kể từ lúc nó bằng nhau

• Sau đó chúng ta sẽ quan tâm đến phần xử lí là đếm số dãy nghịch thế của hoán vị \(perm\)

Ta sẽ duyệt các cặp \((l, r)\) thỏa \(1 \leq l < r \leq n\) và tăng biến đếm lên khi nó nghịch thế (\(l < r\) nhưng \(perm_l > perm_r\))

Kết quả bài toán sẽ là tổng các biến đếm của \(k\) hoán vị kể từ hoán vị \(\pi\)

\(\color{green}{\text{Preference TLE Code }}\): Brute-force

\(^{^{\color{purple}{\text{Complexity : }} O(n^2)\ \color{purple}{\text{query time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int solve(const vector<int> &perm)
{
    int res = 0;
    for (int i = 1; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (perm[i] < perm[j])
                res++;

    return res;
}

\(\color{orange}{\text{Hint 2 <Branch-and-bound>}}\)

• Thay vì tạo tất cả dãy hoán vị, ta sẽ tạo hẳn dãy đầu tiên là \(\pi\) sau đó chạy tiếp \(k\) hoán vị tiếp theo

Ngoài ra còn có cách khác đó là sử dụng chặt nhị phân bằng \(std::next\_permutation()\) để nó đưa ra hoán vị tiếp theo

\(\color{green}{\text{Preference TLE Code }}\): Online Solving

\(^{^{\color{purple}{\text{Complexity : }} O(n + k \times n \times O(query()))\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    cin >> n >> k;
    vector<int> perm(n);
    for (int &x : perm) cin >> x;

    ll res = 0;
    while (k-->0) // duyet 0..k
    {
        res += solve(perm);
        next_permutation(all(perm));
    }

    cout << res;
    return 0;
}

\(\color{goldenrod}{\text{Approach <Divide and Conquer>}}\)

• Ta có thể tiếp cận như này (Paper ở đây)

Chia hoán vị \(P\) thành 2 phần \(P\_left\), \(P\_right\)

Đếm số cặp nghịch đảo trong mỗi phần, chia nó tiếp thành 2 mảng nhỏ hơn

Nếu chỉ còn 1 phần tử, thì ta trả về giá trị 0

Nếu chỉ còn 2 phần tử, thì ta trả về giá trị 1 khi thỏa mãn và 0 khi không thỏa mãn

Số cặp nghịch đảo khi trộn hai mảng \(P\_left\) và \(P\_right\) là tổng các số bé hơn của mảng \(P\_right\) so với mảng \(P\)

• Lưu ý rằng:

Gọi \(C\_left\), \(C\_right\), \(C\_merge\) lần lượt là số cặp nghịch thế được ở \(P\_left\), \(P\_right\), cả \(P\_left\) và \(P\_right\)

Kết quả sẽ là tổng của cả \(C\_left\), \(C\_right\), \(C\_merge\)

Khi \(merge\) 2 mảng \(P\_left\) và \(P\_right\) thì khi \(P\_left_{pl} > P\_right_{pr}\) mình sẽ cộng \(res\) với giá trị \(|P\_left| - pl\)

\(\color{green}{\text{Preference TLE Code }}\): Divide and Conquer

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{query time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int n, k;
ll merge(vector<int> &perm, const vector<int> pleft, const vector<int> pright)
{
    ll res = 0;
    int pl = 0, pr = 0;
    while (pl < pleft.size() && pr < pright.size())
    {
        if (pleft[pl] <= pright[pr])
        {
            perm[pl + pr] = pleft[pl];
            pl++;
        }
        else
        {
            perm[pl + pr] = pright[pr];
            res += int(pleft.size()) - pl;
            pr++;
        }
    }

    while (pl < pleft.size())  { perm[pl + pr] = pleft[pl],  pl++; }
    while (pr < pright.size()) { perm[pl + pr] = pright[pr]; pr++; }

    return res;
}

ll mergesort(vector<int> &perm)
{
    if (perm.size() <= 1) return 0;

    int m = (perm.size() + 1) / 2;
    vector<int> pleft(perm.begin(), perm.begin() + m);
    vector<int> pright(perm.begin() + m, perm.end());
    return mergesort(pleft) + mergesort(pright) + merge(perm, pleft, pright);
}

ll solve(const vector<int> &perm)
{
    vector<int> n_perm(perm);
    return mergesort(n_perm);
}

\(\color{goldenrod}{\text{Approach <Bitwise DnC>}}\)

• Tương tự như trên chúng ta cũng có thể chia để trị dựa trên bitwise

• Bạn nào cần mình giải thích kĩ hơn thì comment bên dưới nhé

\(\color{green}{\text{Preference TLE Code }}\): Bitwise, Divide and Conquer

\(^{^{\color{purple}{\text{Complexity : }} O(n \times \log mask) = O(n \log n) \ \color{purple}{\text{query time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int n, k;
int upper_power_of_two(int v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;
}

ll solve(const vector<int> &perm, int mask = upper_power_of_two(n))
{
    if (!mask || perm.empty()) return 0;

    ll res = 0;
    vector<int> pleft, pright;
    for (int x : perm)
    {
        if (x & mask)
            pleft.push_back(x & $mask);
        else
        {
            res += pleft.size();
            pright.push_back(x & $mask);
        }
    }

    return res + solve(pleft, mask >> 1) + solve(pright, mask >> 1);
}

\(\color{green}{\text{Preference TLE Code }}\): Bitwise, Divide and Conquer

\(^{^{\color{purple}{\text{Complexity : }} O(n \times w) = O(n) = O(n \log n) \ \color{purple}{\text{query time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int n, k;
ll solve(const vector<int> &perm, int bit = 17)
{
    if (!bit || perm.empty()) return 0;

    ll res = 0;
    int mask = (1 << bit);
    vector<int> pleft, pright;
    for (int x : perm)
    {
        if (x & mask)
            pleft.push_back(x & $mask);
        else
        {
            res += pleft.size();
            pright.push_back(x & $mask);
        }
    }

    return res + solve(pleft, bit - 1) + solve(pright, bit - 1);
}

\(\color{goldenrod}{\text{Approach <Fenwick Tree>}}\)

• Ta có thể tiếp cận như này

Gọi \(C_x\) là số lượng giá trị \(x\) đã xuất hiện.

Với mỗi vị trí \(i\) ta đếm số lượng những số \(> P_j (j < i)\), hay lấy số lượng những số \(\geq P_i + 1\)

Duyệt các phần tử \(P_i\) từ đầu dãy tới cuối dãy tính tổng từ \(C_{P_i+1}\) đến cuối mảng \(C\) rồi thêm vào kết quả

• Lí do ta dùng Fenwick Tree

Cập nhật các số từ \(C_1 \rightarrow C_{P_i}\) lên 1 đơn vị trong \(O(\log n)\)

Tính tổng các số từ \(C_{P_i} \rightarrow C_n\) trong \(O(\log n)\)

• Lưu ý rằng implementation ở dưới sử dụng one-based BIT, để dùng zero-based BIT thì ta phải giảm giá trị \(p\) xuống 1 đơn vị

\(\color{green}{\text{Preference TLE Code }}\): Fenwick Tree

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{query time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int n, k;
vector<ll> BIT; /// Fenwick Tree
void update(int p) {
    for (p--; p > 0; p -= p & -p)
        BIT[p]++;
}

ll getValue(int p) {
    ll res = 0;
    for (p--; p <= n; p += p & -p)
        res += BIT[p];

    return res;
}

ll solve(const vector<int> &perm)
{
    ll res = 0;
    BIT.assign(n + 1, 0);    

    for (int x : perm)
    {
        res += getValue(x);
        update(x);
    }
    return res;
}

\(\color{orange}{\text{Hint 3 <Dynamic-programming>}}\)

• Để có thể giải được bài này với \(k\) lớn, chúng ta sẽ sử dụng quy hoạch động lưu lại các giá trị đã tính trước đó

• Gọi \(cal_x\) là kết quả của việc đếm số lượng cặp nghịch thế trong đoạn \([1, x]\)

\(cal_x = constant 0\) với \(x = 0\)

\(cal_x = cal_{x - 1} + getValue(perm_i)\) với \(x > 0\)

• Nhận xét rằng khi ta lấy hoán vị tiếp theo, phần đầu nó có thể không đổi

Gọi \(n\_perm\) là hoán vị tiếp theo của \(perm\)

Gọi \(p\) là vị trí đầu tiêniên mà \(perm_p \neq n\_perm_p\)

Đây ta sẽ định nghĩa \(perm_0 = n\_perm_0 = 0\)

Lúc này ta chỉ cần đảo lại (reverse) lại các giá trị trước đó của \(perm_p \rightarrow perm_n\)

Sau đó chúng ta tính tiếp từ \(cal_p \rightarrow cal_n\)

Kết quả cho một hoán vị như thế là \(cal_n\)

\(\color{green}{\text{Preference TLE Code }}\): Online Solving, Fenwick Tree, Dynamic programming

\(^{^{\color{purple}{\text{Complexity : }} O((k \times n + n) \log n))\ \color{purple}{\text{query time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int n, k;
vector<ll> BIT;

void update(int p) {
    for (p--; p > 0; p -= p & -p)
        BIT[p]++;
}

void reverse(int p) {
    for (p--; p > 0; p -= p & -p)
        BIT[p]--;
}

ll getValue(int p) {
    ll res = 0;
    for (; p <= n; p += p & -p)
        res += BIT[p];

    return res;
}

int main()
{
    cin >> n >> k;
    if (k == 0) return cout << 0, 0;

    vector<int> perm(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> perm[i];

    vector<ll> cal(n + 1, 0);
    BIT.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        cal[i] = cal[i - 1] + getValue(perm[i]);
        update(perm[i]);
    }

    ll res = cal[n];
    vector<int> n_perm(perm);
    while (0<--k) /// duyet 1..k
    {
        next_permutation(all(n_perm));
        int p;
        for (p = 1; p <= n; ++p)
            if (perm[p] != n_perm[p]) 
                { p--; break; }

        for (int i = p; i <= n; ++i)
            reverse(perm[i]);

        for (int i = p; i <= n; ++i)
        {
            cal[i] = cal[i - 1] + getValue(n_perm[i]);
            update(n_perm[i]);
        }

        res += cal[n];
        next_permutation(all(perm));
    }
    cout << res;
    return 0;
}

\(\color{orange}{\text{Hint 4 <Binary Search>}}\)

• Để ý kĩ thì giữa 2 hoán vị liền nhau có một điều đặc biệt

Với \(p\) là vị trí đầu tiên mà \(perm_p \neq n\_perm_p\)

Khi đó có \(perm[p+1\dots n]\) là dãy số giảm trong khi \(n\_perm[p+1\dots n]\) là dãy số tăng

Do đó có thể tìm vị trí thỏa mãn bằng chặt nhị phân

• Chúng ta có thể chặt nhị phân để tìm kiếm vị trí \(p\) đầu tiên (và cũng là lớn nhất) thỏa \(perm_p \neq n\_perm_p\)

Chặt nhị phân với \((l, r) = (1, n)\) và \(m = \lfloor \frac{l + r}{2} \rfloor\)

\(m\) là vị trí thỏa mãn khi và chỉ khi (\(perm_{m} \neq n\_perm_{m}\)) và (\(perm_{m - 1} \neq n\_perm_{m - 1}\))

Khi \(m\) thỏa mãn, ta cập nhật \(p = m\) và di chuyển con trỏ \(l = m + 1\)

Khi \(m\) không thỏa mãn ta di chuyển con trỏ \(r = m - 1\)

\(\color{green}{\text{Preference AC Code }}\): Online Solving, Fenwick Tree, Dynamic programming, Binary Search

\(^{^{\color{purple}{\text{Complexity : }} O((k \times inverse\_factorial(k) + n) \log alphabet) = O((n! \times n + n) \log_2 n) = O(k \log_2 n) \ {\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    getUnsign(n, k);
    if (k == 0) return cout << 0, 0;

    vector<int> perm(n + 1);
    for (int i = 1; i <= n; ++i)
        getUnsign(perm[i]);

    vll cal(n + 1, 0);
    BIT.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        cal[i] = cal[i - 1] + getValue(perm[i]);
        update(perm[i]);
    }

    ll res = cal[n];
    vector<int> n_perm(perm);
    while (0<--k)
    {
        next_permutation(all(n_perm));
        int p = 1;
        for (int l = 1, r = n; l <= r; )
        {
            int m = (l + r) / 2;
            if (perm[m] == n_perm[m] && perm[m - 1] == n_perm[m - 1])
            {
                p = m;
                l = m + 1;
            }
            else 
                r = m - 1;
        }

        for (int i = p; i <= n; ++i)
            reverse(perm[i]);

        for (int i = p; i <= n; ++i)
        {
            cal[i] = cal[i - 1] + getValue(n_perm[i]);
            update(n_perm[i]);
        }
        res += cal[n];

        next_permutation(all(perm));
    }
    cout << res;
    return 0;
}