04-21 20:14 已编辑牛客小学算法工程师发布于湖南

关注

题解 | 【模板】康托展开 #

奶牛排排站

https://www.nowcoder.com/practice/15d024fccb7348bf872f5c1af899e825?tpId=388&tqId=11306679&channelPut=tracker1

$[模板+康托展开+权值线段树]$

康托展开：现在给你一个长度为 $n$ 排列，求这个排列在长度为 $n$ 的所有排列中是第几个排列(即求其排名)。

假设现在的排列是 $[a_{1},a_{2},a_{3},...,a_{n}]$

那么排名等于 $\sum_{i=1}^{n}{(sum_{i}\times (n-i)!)} + 1$ ，其中 $sum[i]$ 表示在剩余数组里面有多少个比 $a_{i}$ 小的数的个数

例如排列 $[3,2,4,1,5]$

$int\ ans = 0$

$i=1$ 时，剩余数组为 $[3,2,4,1,5]$ ，里面有 $2$ 个数比 $a_{1}=3$ 小，所以 $ans+=2\times (4!) =ans+=48$

$i=2$ 时，剩余数组为 $[2,4,1,5]$ ，里面有 $1$ 个数比 $a_{2}=2$ 小，所以 $ans+=1\times (3!) =ans+=6$

$i=3$ 时，剩余数组为 $[4,1,5]$ ，里面有 $1$ 个数比 $a_{3}=4$ 小，所以 $ans+=1\times (2!) =ans+=2$

$i=4$ 时，剩余数组为 $[1,5]$ ，里面有 $0$ 个数比 $a_{4}=1$ 小，所以 $ans+=0\times (1!) =ans+=0$

$i=5$ 时，剩余数组为 $[5]$ ，里面有 $0$ 个数比 $a_{5}=5$ 小，所以 $ans+=0\times (0!) =ans+=0$

所以排列 $[3,2,4,1,5]$ 的排名为 $56+1=57$

为什么加 $1$ ，因为 $\sum_{i=1}^{n}{(sum_{i}\times (n-i)!)}$ 这个式子求的是排列 $[3,2,4,1,5]$ 前面有多少个排列，那么 $[3,2,4,1,5]$ 的排名就需要加上 $1$

使用权值线段树解决： $sum_{i}=query(1,1,a[i]-1)$ ，特判 $a[i]=1$ 的情况；然后将 $a[i]$ 删除掉，即 $modify(1,a[i],-1)$

逆康托展开：现在给你排名 $x$ ，求长度为 $n$ 的排列中第 $x$ 的排列是什么。

假设 $n=5$ ，求第 $10$ 个排列是什么

首先需要 $x$ 减去 $1$ ，那么 $x=9$

一开始排列为 $[1,2,3,4,5]$

$i=1$ 时，剩余数组为 $[1,2,3,4,5]$ ， $x=9$ ， $k=9/(4!)=0$ ， $r=9\ mod\ (4!)=9$ ，那么排列的第 $1$ 个数为剩余数组里面的第 $(k+1)=1$ 个数，即 $1$

$i=2$ 时，剩余数组为 $[2,3,4,5]$ ， $x=9$ ， $k=9/(3!)=1$ ， $r=9\ mod\ (3!)=3$ ，那么排列的第 $2$ 个数为剩余数组里面的第 $(k+1)=2$ 个数，即 $3$

$i=3$ 时，剩余数组为 $[2,4,5]$ ， $x=3$ ， $k=3/(2!)=1$ ， $r=3\ mod\ (2!)=1$ ，那么排列的第 $3$ 个数为剩余数组里面的第 $(k+1)=2$ 个数，即 $4$

$i=4$ 时，剩余数组为 $[2,5]$ ， $x=1$ ， $k=1/(1!)=1$ ， $r=1\ mod\ (1!)=0$ ，那么排列的第 $4$ 个数为剩余数组里面的第 $(k+1)=2$ 个数，即 $5$

$i=5$ 时，剩余数组为 $[2]$ ， $x=0$ ， $k=0/(0!)=0$ ， $r=0\ mod\ (0!)=0$ ，那么排列的第 $5$ 个数为剩余数组里面的第 $(k+1)=1$ 个数，即 $2$

所以排列为 $[1,3,4,5,2]$

同样使用权值线段树解决，处理第 $i$ 个位置时， $k=x/(n-i)!$ ， $r=x\ mod\ (n-i)!$ ；主要是如何求剩余数组里面第 $(k+1)$ 个数，显然权值线段树基操，然后删除就是 $modify(1,a[i],-1)$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 25;

struct Node{
    int l, r;
    int cnt;
}tr[4 * N];

int n, q, f[25];

void push_up(int u){
    tr[u].cnt = (tr[u << 1].cnt + tr[u << 1 | 1].cnt);
}

void build(int u, int l, int r){
    if(l == r) tr[u] = {l, r, 0};
    else{
        tr[u] = {l, r, 0};
        int mid = (tr[u].l + tr[u].r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
}

void modify(int u, int pos, int v){
    if(tr[u].l == pos && pos == tr[u].r) tr[u].cnt += v;
    else{
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(pos <= mid) modify(u << 1, pos, v);
        else modify(u << 1 | 1, pos, v);
        push_up(u);
    }
}

int query_k(int u, int pos){
    if(tr[u].l == tr[u].r) return tr[u].l;
    else{
        if(pos <= tr[u << 1].cnt) return query_k(u << 1, pos);
        else return query_k(u << 1 | 1, pos - tr[u << 1].cnt);
    }
}

int query_sum(int u, int l, int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].cnt;
    else{
        int sum = 0;
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) sum += query_sum(u << 1, l, r);
        if(r > mid) sum += query_sum(u << 1 | 1, l, r);
        return sum;
    }
}

signed main(){
    HelloWorld;

    f[0] = 1;
    for(int i = 1; i <= 20; i ++) f[i] = f[i - 1] * i;
    cin >> n >> q;
    build(1, 1, n);

    while(q --){
        char op; cin >> op;
        if(op == 'P'){
            int x; cin >> x;
            x -= 1;
            for(int i = 1; i <= n; i ++) modify(1, i, 1);
            for(int i = 1; i <= n; i ++){
                int sum = query_k(1, x / f[n - i] + 1);
                cout << sum << " ";
                x %= f[n - i];
                modify(1, sum, -1);
            }
            cout << endl;
        }
        else{
            vector<int> a(n + 1);
            for(int i = 1; i <= n; i ++){
                cin >> a[i];
                modify(1, i, 1);
            }
            int ans = 0;
            for(int i = 1; i <= n; i ++){
                if(a[i] == 1) modify(1, 1, -1);
                else{
                    int sum = query_sum(1, 1, a[i] - 1);
                    ans += sum * f[n - i];
                    modify(1, a[i], - 1);
                }
            }
            cout << ans + 1 << endl;
        }
    }
    return 0;
}