题解 | 奶牛排排站

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

class bit {
    int n;
    vector<int> tree;

public:
    bit(int n):n(n),tree(n+1) {}


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

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

    int query(int x) {
    int res = 0;
    for (; x; x &= x - 1) {
      res += tree[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+tree[x] >= k) {
                x -= 1<<i;
            } else {
                ps += tree[x];
            }
        }
        return x+1;
    }
};

ll find(const vector<int>& nums) {
    int n = nums.size();
    bit bits(n);
    ll f = 1;
    ll ans = 0;
    for(int i = n-1;i>=0;i--) {
        ans += bits.query(nums[i]-1)*f;
        bits.add(nums[i],1);
        f *= n-i;
    }
    return ans+1;
}

vector<int> find_per(long long k,int n) {
    k-=1;
    vector<int> le(n);
    for(int i = 1;i<=n;i++) {
        le[n-i] = k%i;
        k/=i;
    }
    bit bits(n);
    bits.fill();
    vector<int> res(n);
    for(int i = 0;i<n;i++) {
        res[i] = bits.find_kth(le[i]+1);
        bits.add(res[i],-1);
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,k;cin >> n >> k;
    vector<int> Bi(n);
    char opt;ll Ai;
    for(int i = 1;i<=k;i++) {
        cin >> opt;
        if(opt == 'P') {
            cin >> Ai;
            auto ans = find_per(Ai,n);
            for(int& i:ans) {
                cout << i << ' ';
            }
            cout << endl;
        } else {
            for(int& i:Bi) {
                cin >> i;
            }
            cout << find(Bi) << endl;
        }
    }
    return 0;
}

很奇怪，明明很难的板子，怎么这么多人AC

康托展开很好写，但是逆展开太逆天了