#include <iostream>#include <vector>// Merge sort and count inversions.long long merge_sort(std::vector<int>& nums, int b, int e) { // Return 0 when length <= 1. if (e - b <= 1) return 0; long long res = 0; int m = (b + e) / 2; // Merge_sort two halves. res += merge_sort(nums, b, m); res += merge_sort(nums, m, e); // Temporary vector to store sorted array. std::vector<int> tmp(e - b); int i = b, j = m, k = 0; while (i < m && j < e) { if (nums[j] < nums[i]) { tmp[k] = nums[j++]; // In this case, all elements in [i,m) are larger than element j. res += m - i; } else { tmp[k] = nums[i++]; } ++k; } // Deal with remaining elements. for (; i < m; ++i, ++k) { tmp[k] = nums[i]; } for (; j < e; ++j, ++k) { tmp[k] = nums[j]; } // Copy back to original vector. for (i = b, k = 0; i < e; ++i, ++k) { nums[i] = tmp[k]; } return res;}int main() { int n; std::cin >> n; std::vector<int> nums(n); for (int& num : nums) { std::cin >> num; } std::cout << merge_sort(nums, 0, n); return 0;}
树状数组
#include <algorithm>#include <iostream>#include <unordered_map>#include <vector>// A simple BIT implementation.class BIT { int n; std::vector<int> su; public: BIT(int n) : n(n), su(n + 1) {} // Add v to the x-th number. void add(int x, int v) { for (; x <= n; x += x & (-x)) { su[x] += v; } } // Get the cumulative sum till the x-th number. int query(int x) { int res = 0; for (; x; x &= x - 1) { res += su[x]; } return res; }};// Count inversions.long long solve(const std::vector<int>& nums) { // Discretization. std::vector<int> sorted(nums); std::sort(sorted.begin(), sorted.end()); sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end()); std::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;}int main() { int n; std::cin >> n; std::vector<int> nums(n); for (int& num : nums) { std::cin >> num; } std::cout << solve(nums); return 0;}
#include <iostream>#include <vector>// A simple BIT implementation.class BIT { int n; std::vector<int> su; public: BIT(int n) : n(n), su(n + 1) {} // Add v to the x-th number. void add(int x, int v) { for (; x <= n; x += x & (-x)) { su[x] += v; } } // Get the cumulative sum till the x-th number. int query(int x) { int res = 0; for (; x; x &= x - 1) { res += su[x]; } return res; }};// Get the rank of a permutation of 1~n.long long find_rank(const std::vector<int>& nums) { int n = nums.size(); BIT bit(n); long long fac = 1; long long res = 0; // Reverse iteration. for (int i = n - 1; i >= 0; --i) { // Count the number of elements smaller than the current one. res += bit.query(nums[i] - 1) * fac; // Insert the current element into the BIT. bit.add(nums[i], 1); // Update the factorial. fac *= n - i; } return res + 1;}int main() { int n; std::cin >> n; std::vector<int> nums(n); for (int& num : nums) { std::cin >> num; } std::cout << find_rank(nums); return 0;}
求给定排名的排列
#include <cmath>#include <iostream>#include <vector>// A simple BIT implementation.class BIT { int n; std::vector<int> su; public: BIT(int n) : n(n), su(n + 1) {} // Fill the BIT with one. void fill() { for (int x = 1; x <= n; ++x) { su[x] += x & (-x); } } // Add v to the x-th number. void add(int x, int v) { for (; x <= n; x += x & (-x)) { su[x] += v; } } // Get the k-th smallest element. 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; }};// Find the k-th permutation of 1~n.std::vector<int> find_permutation(int n, long long k) { --k; // Expand rank to Lehmer code. std::vector<int> lehmer(n); for (int i = 1; i <= n; ++i) { lehmer[n - i] = k % i; k /= i; } BIT bit(n); // Set all values in BIT to one. bit.fill(); std::vector<int> res(n); for (int i = 0; i < n; ++i) { // Find the lehmer[i]-th smallest unused element. res[i] = bit.find_kth(lehmer[i] + 1); // Remove it from the BIT. bit.add(res[i], -1); } return res;}int main() { int n; long long k; std::cin >> n >> k; auto res = find_permutation(n, k); for (int num : res) { std::cout << num << ' '; } return 0;}