排列

注意，这里指的不是排列数，而是全排列

若一个集合\(X\)本身具有自然顺序，我们称这个集合的置换（改变元素顺序）为排列

排列可以看作置换的结果

逆序数

在一个排列中，如果某一个较大的数排在某一个较小的数前面，我们说这两个数构成一个逆序

在一个排列中出现的逆序总个数称为这个置换的逆序数，排列的逆序数是它恢复成正序序列所需要做相邻对换的最少次数。因而，排列的逆序数的奇偶性与相应的置换的奇偶性一致

可以使用树状数组求解逆序数个数

class BIT {
  int n;
  vector<int> su;

 public:
  BIT(int n) : n(n), su(n + 1) {}

  void add(int x, int v) {
    for (; x <= n; x += x & (-x)) {
      su[x] += v;
    }
  }

  int query(int x) {
    int res = 0;
    for (; x; x &= x - 1) {
      res += su[x];
    }
    return res;
  }
};

long long solve(const vector<int>& nums) {
  vector<int> sorted(nums);
  sort(sorted.begin(), sorted.end());
  sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
  unordered_map<int, int> ids;
  int m = sorted.size();
  for (int i = 0; i < m; ++i) {
    // Reverse the order.
    // Now a smaller id means a larger element.
    ids[sorted[i]] = m - i;
  }
  // Main part.
  BIT bit(m);
  long long res = 0;
  for (int num : nums) {
    int id = ids[num];
    // Get inversion pair (i,j) with j the current element.
    // Namely, count the number of elements larger than
    //     the current one but located before it.
    res += bit.query(id - 1);
    // Insert the current element to the BIT.
    bit.add(id, 1);
  }
  return res;
}

顺序

排列之间可以比较大小，排列的顺序就是这个字符串上的字典序

可以使用prev_permutation和next_permutation找到当前排列按照字典序的上一个和下一个排列

排名

将\(n\)个元素的排列按照字典序从小到大列举出来，则某一排列在这个序列中的位次就是该排列的排名，它建立了排列与正整数之间的一一对应，常用于排列相关问题的状态压缩

我们通常称这个排名为排列的康托展开，更严谨的说，一个排列的排名的康托展开，对应着该排列的Lehmer码

康托展开指一种将自然数展开为数列的方法，也称为阶乘进制，这种进制中，不同数位对应的底数并不相同，如十进制数\(463_{10}=341010_!\)表示如下含义：

\(463=3\times 5!+4\times4!+1\times3!+0\times2!+1\times1!+0\times0!\)

故我们可以使用康托展开计算排列的排名：

将给定长度为\(n\)的排列转化为Lehmer码，即一个长度为\(n\)的序列，其中第\(i\)位是在排列中，排在第\(i\)位后面，但是却比第\(i\)位元素小的元素个数，它等于尚未使用的元素中给定元素的排名（减一）
将Lehmer码看作是自然数的康托展开，求出原来的自然数并加一，则最终排名为

\(\text{rank }\sigma=1+L_{\sigma}(1)(n-1)!+L_{\sigma}(2)(n-2)!+\cdots+L_{\sigma}(n)(0)!\)

如果要求排名对应的排列，只要将上述过程反过来即可，球的Lehmer码中的数字之和就是排列的逆序数

可以通过树状数组进行计算

e.g. 奶牛排排站

#include <bits/stdc++.h>
#include <cstdio>
using ll = long long;
using namespace std;
ll n, k;

class BIT {
  int n;
  std::vector<int> su;

 public:
  BIT(int n) : n(n), su(n + 1) {}

  void fill() {
    for (int x = 1; x <= n; ++x) {
      su[x] += x & (-x);
    }
  }

  void add(int x, int v) {
    for (; x <= n; x += x & (-x)) {
      su[x] += v;
    }
  }
  int query(int x) {
    int res = 0;
    for (; x; x &= x - 1) {
      res += su[x];
    }
    return res;
  }

  int find_kth(int k) {
    int ps = 0, x = 0;
    for (int i = log2(n); i >= 0; --i) {
      x += 1 << i;
      if (x >= n || ps + su[x] >= k) {
        x -= 1 << i;
      } else {
        ps += su[x];
      }
    }
    return x + 1;
  }
};
// 给定排名求对应排列
void P(){
    ll a;
    cin >> a;
    a--;
    vector<ll> lehmer(n);
    for (int i = 1; i<=n; i++){
        lehmer[n-i] = a%i;
        a/=i;
    }
    BIT bit(n);
    bit.fill();
    vector<ll> re(n);

    for (int i = 0; i<n; i++){
        re[i] = bit.find_kth(lehmer[i]+1);
        bit.add(re[i],-1);
    }
    for (auto it: re) cout << it <<" ";
    cout << endl;
}
// 给定排列求对应排名
void Q(){
    vector<ll> q(n);
    for (int i = 0; i<n; i++){
        cin >> q[i];
    }
    BIT bit(n);
    ll fac = 1;
    ll res = 0;
    for (int i = n-1; i>=0; i--){
        res+=bit.query(q[i]-1)*fac;
        bit.add(q[i],1);
        fac*=(n-i);
    }
    cout << res+1<<endl;
}
int main() {
    cin >> n >> k;
    while(k--){
        char op;
        cin >> op;
        if (op=='P') P();
        else Q();
    }
}

红魔咖啡馆

【数学】排列

排列

逆序数

顺序

排名