题解 | 奶牛排排站

康托展开的板子题，需要先学习康托展开知识点才能写这个题。

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 2e5 + 5, mod =998244353, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){  
    int n,k;
    cin>>n>>k;

    vector<ll>fact(n+5);
    fact[0]=1;
    for(int i=1;i<=n;i++)fact[i]=fact[i-1]*i;

    auto get_rank=[&](const vector<int>&a)->ll{
        ll ans=0;
        for(int i=1;i<=n;i++){
            ll cnt=0;
            for(int j=i+1;j<=n;j++){
                cnt+=a[i]>a[j];
            }
            ans+=cnt*fact[n-i];
        }
        return ans+1;
    };

    auto get_v=[&](ll x)->vector<int>{
        vector<int>a(n+1);
        vector<bool>vis(n+1,false);
        for(int i=1;i<=n;i++){
            ll now=x/fact[n-i];
            x%=fact[n-i];
            for(int j=1;j<=n;j++){
                if(!vis[j]){
                    if(now==0){
                        a[i]=j;
                        vis[j]=true;
                        break;
                    }
                    now--;
                }
            }
        }
        return a;
    };
    while(k--){
        char op;
        cin>>op;
        if(op=='P'){
            ll x;
            cin>>x;
            auto a=get_v(x-1);
            for(int i=1;i<=n;i++){
                cout<<a[i]<<" \n"[i==n];
            }
        }else{
            vector<int>a(n+1);
            for(int i=1;i<=n;i++)cin>>a[i];
            cout<<get_rank(a)<<'\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    // cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}