康拓展开

康托展开

康托展开是用来干这个的：求 (1sim N) 的一个给定全排列在所有 (1sim N) 全排列中的排名。

公式就是这个(ans = 1 + displaystyle sum_{i = 1}^{n} A[i] * (n - i)!)

(A[i])表示(i + 1 sim n)中的数字比(i)上的数字小的个数。

为啥呢？可以这么理解，枚举到第(i)位了，那前(i - 1)位肯定一样，第(i)位上可以填的数就是之前没用过的，比(i)上的数字小的数，也就是(A[i])，那(i)位之后怎么填就都可以了，也就是((n - i)!)。

得用树状数组维护一下，不然会(TLE)。

#include <bits/stdc++.h>

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 1e6 + 5, mod = 998244353;
int n, ans, fac, a[N], t[N];

int lowbit(int x) { return x & -x; }

void change(int x) { for(; x <= N - 5; x += lowbit(x)) t[x] ++; }

int query(int x) { int res = 0; for(; x ; x -= lowbit(x)) res += t[x]; return res; }

int main() {

    n = read(); fac = 1;
    for(int i = 1;i <= n; i++) a[i] = read();
    for(int i = n;i >= 1; i--) {
        int tmp = query(a[i]);
        ans = (ans + 1ll * tmp * fac % mod) % mod;
        fac = 1ll * fac * (n - i + 1) % mod;
        change(a[i]);
    }
    printf("%d", ans + 1);

    return 0;
}

逆康拓展开

UVA11525 Permutation

问题是一样的，就是反过来了，给你一个排名，让你求对应的排列。

因为这个排名太大了，题目给了你所有的(A[i])，这就好办了。我们开一颗权值线段树，每次找其中的第(A[i])大值，并不断删点就好了。

#include <bits/stdc++.h>

#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)
#define mid ((l + r) >> 1)

using namespace std;

inline long long read() {
    long long s = 0, f = 1; char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
    for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
    return s * f;
}

const int N = 5e4 + 5;
int T, n, s;
int t[N << 2];

void build(int o, int l, int r) {
    if(l == r) { t[o] = 1; return ; }
    build(ls(o), l, mid); build(rs(o), mid + 1, r);
    t[o] = t[ls(o)] + t[rs(o)];
}

int query(int o, int l, int r, int k) {
    t[o] --; if(l == r) return l;
    if(t[ls(o)] < k) return query(rs(o), mid + 1, r, k - t[ls(o)]);
    return query(ls(o), l, mid, k);
}

int main() {

    T = read();
    while(T --> 0) {
        n = read(); build(1, 1, n);
        for(int i = 1;i <= n; i++) {
            s = read(); 
            if(i != n) printf("%d ", query(1, 1, n, s + 1));
            if(i == n) printf("%d
", query(1, 1, n, s + 1)); //坑点
        }
    }

    return 0;
}