题解 | #奶牛排排站#

题目链接

题目描述

在 $N$ 个元素的全排列中，建立排列与它按字典序的排名之间的一一对应关系。需要支持两种操作：

Q 操作：给定一个排列，求出它的排名（从 1 开始）。
P 操作：给定一个排名，求出对应的排列。

这个问题是康托展开 (Cantor Expansion) 及其逆运算的典型应用。

解题思路

康托展开：排列求排名 (Q 操作)

康托展开的公式为： $X = a_n(n-1)! + a_{n-1}(n-2)! + \dots + a_1 \cdot 0!$ 其中， $a_i$ 表示在当前位右边（未出现的数字中）比第 $i$ 位数字小的数字的个数。最终排名为 $X+1$ 。

举例说明：求排列 {1, 2, 5, 3, 4} 在 $N=5$ 的全排列中的排名。

第一位是 1：比 1 小的数有 0 个。贡献为 $0 \times 4! = 0$ 。
第二位是 2：在剩下的 {2, 3, 4, 5} 中，比 2 小的数有 0 个。贡献为 $0 \times 3! = 0$ 。
第三位是 5：在剩下的 {3, 4, 5} 中，比 5 小的数有 2 个 (3, 4)。贡献为 $2 \times 2! = 4$ 。
第四位是 3：在剩下的 {3, 4} 中，比 3 小的数有 0 个。贡献为 $0 \times 1! = 0$ 。
第五位是 4：在剩下的 {4} 中，比 4 小的数有 0 个。贡献为 $0 \times 0! = 0$ 。

总和 $X = 0 + 0 + 4 + 0 + 0 = 4$ 。排名为 $X+1=5$ 。

为了高效地计算“未出现的数字中比当前数字小的个数”，我们可以使用树状数组 (Fenwick Tree)。初始时，树状数组记录所有数字都存在。每使用一个数字，就将其在树状数组中标记为不存在（值减 1）。查询时，我们只需要查询树状数组的前缀和即可。

逆康托展开：排名求排列 (P 操作)

这是康托展开的逆过程。给定排名 $K$ ，我们从高位到低位依次确定排列的每一位。首先，将排名 $K$ 减 1，得到康托展开值 $X$ 。

用 $X$ 除以 $(n-1)!$ ，商 $q_1$ ，余数 $r_1$ 。 $q_1$ 表示在当前所有可用数字中，有多少个比我们要找的数字小。所以，我们应该选择第 $q_1+1$ 小的可用数字作为排列的第一位。
用 $r_1$ 除以 $(n-2)!$ ，商 $q_2$ ，余数 $r_2$ 。在剩下的可用数字中，选择第 $q_2+1$ 小的数作为第二位。
... 以此类推，直到确定所有位。

同样，为了高效查找“第 k 小的可用数字”，我们可以使用树状数组。在初始满的树状数组上进行二分查找或倍增，找到前缀和恰好为 $k$ 的位置。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

using namespace std;
using ll = long long;

const int MAXN = 21;
ll fact[MAXN];
int n;
vector<int> bit;

void update(int i, int delta) {
    for (; i <= n; i += i & -i) {
        bit[i] += delta;
    }
}

int query(int i) {
    int sum = 0;
    for (; i > 0; i -= i & -i) {
        sum += bit[i];
    }
    return sum;
}

int find_kth(int k) {
    int pos = 0;
    int current_sum = 0;
    int log_n = 0;
    if (n > 0) log_n = floor(log2(n));

    for (int i = 1 << log_n; i > 0; i >>= 1) {
        if (pos + i <= n && current_sum + bit[pos + i] < k) {
            current_sum += bit[pos + i];
            pos += i;
        }
    }
    return pos + 1;
}

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = fact[i - 1] * i;
    }
}

void solve() {
    int q;
    cin >> n >> q;
    precompute_factorials();

    while (q--) {
        char type;
        cin >> type;
        if (type == 'P') {
            ll k;
            cin >> k;
            k--; // 0-indexed rank

            bit.assign(n + 1, 0);
            for (int i = 1; i <= n; ++i) {
                update(i, 1);
            }

            vector<int> p(n);
            for (int i = 0; i < n; ++i) {
                ll divisor = fact[n - 1 - i];
                ll quotient = k / divisor;
                k %= divisor;
                
                int num = find_kth(quotient + 1);
                p[i] = num;
                update(num, -1);
            }

            for (int i = 0; i < n; ++i) {
                cout << p[i] << (i == n - 1 ? "" : " ");
            }
            cout << "\n";

        } else { // type == 'Q'
            vector<int> p(n);
            bit.assign(n + 1, 0);
            for (int i = 1; i <= n; ++i) {
                update(i, 1);
            }

            ll rank = 0;
            for (int i = 0; i < n; ++i) {
                cin >> p[i];
                rank += (ll)(query(p[i] - 1)) * fact[n - 1 - i];
                update(p[i], -1);
            }
            cout << rank + 1 << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static final int MAXN = 21;
    static long[] fact = new long[MAXN];
    static int n;
    static int[] bit;

    static void update(int i, int delta) {
        for (; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    static int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) {
            sum += bit[i];
        }
        return sum;
    }

    static int find_kth(int k) {
        int pos = 0;
        int current_sum = 0;
        int log_n = (n > 0) ? (int) (Math.log(n) / Math.log(2)) : -1;

        for (int i = 1 << log_n; i > 0; i >>= 1) {
            if (pos + i <= n && current_sum + bit[pos + i] < k) {
                current_sum += bit[pos + i];
                pos += i;
            }
        }
        return pos + 1;
    }
    
    static void precompute_factorials() {
        fact[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            fact[i] = fact[i - 1] * i;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        
        precompute_factorials();

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            char type = st.nextToken().charAt(0);
            st = new StringTokenizer(br.readLine());

            if (type == 'P') {
                long k = Long.parseLong(st.nextToken());
                k--; // 0-indexed

                bit = new int[n + 1];
                for (int j = 1; j <= n; j++) {
                    update(j, 1);
                }

                int[] p = new int[n];
                for (int j = 0; j < n; j++) {
                    long divisor = fact[n - 1 - j];
                    long quotient = k / divisor;
                    k %= divisor;

                    int num = find_kth((int) quotient + 1);
                    p[j] = num;
                    update(num, -1);
                }

                for (int j = 0; j < n; j++) {
                    out.print(p[j] + (j == n - 1 ? "" : " "));
                }
                out.println();
            } else { // type == 'Q'
                bit = new int[n + 1];
                for (int j = 1; j <= n; j++) {
                    update(j, 1);
                }
                
                long rank = 0;
                for (int j = 0; j < n; j++) {
                    int val = Integer.parseInt(st.nextToken());
                    rank += (long) (query(val - 1)) * fact[n - 1 - j];
                    update(val, -1);
                }
                out.println(rank + 1);
            }
        }
        out.flush();
    }
}

import sys

MAXN = 21
fact = [0] * MAXN
n = 0
bit = []

def update(i, delta):
    while i <= n:
        bit[i] += delta
        i += i & -i

def query(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

def find_kth(k):
    pos = 0
    current_sum = 0
    log_n = n.bit_length() - 1
    
    for i in range(log_n, -1, -1):
        step = 1 << i
        if pos + step <= n and current_sum + bit[pos + step] < k:
            current_sum += bit[pos + step]
            pos += step
    return pos + 1

def precompute_factorials():
    fact[0] = 1
    for i in range(1, MAXN):
        fact[i] = fact[i - 1] * i

def main():
    global n, bit
    input = sys.stdin.readline
    
    precompute_factorials()
    
    first_line = input().strip()
    if not first_line:
        return
    n_str, q_str = first_line.split()
    n, q = int(n_str), int(q_str)
    
    for _ in range(q):
        type_line = input().strip()
        data_line = input().strip()

        if type_line == 'P':
            k = int(data_line)
            k -= 1

            bit = [0] * (n + 1)
            for i in range(1, n + 1):
                update(i, 1)
            
            p = []
            for i in range(n):
                divisor = fact[n - 1 - i]
                quotient = k // divisor
                k %= divisor
                
                num = find_kth(quotient + 1)
                p.append(num)
                update(num, -1)
            
            print(*p)

        else: # type_line == 'Q'
            p = list(map(int, data_line.split()))
            bit = [0] * (n + 1)
            for i in range(1, n + 1):
                update(i, 1)

            rank = 0
            for i in range(n):
                rank += query(p[i] - 1) * fact[n - 1 - i]
                update(p[i], -1)
            print(rank + 1)

if __name__ == "__main__":
    main()

算法及复杂度

算法：康托展开 / 逆康托展开 + 树状数组优化
时间复杂度： $O(Q \cdot N \log N)$ 。每次查询需要进行 $N$ 次操作，每次操作中，树状数组的查询或查找（query 或 find_kth）的复杂度为 $O(\log N)$ 。
空间复杂度： $O(N)$ ，用于存储树状数组和预计算的阶乘。