康托展开¶

康托展开（Cantor expansion）是一种将自然数映射到自然数序列的数学方法，通常用于组合数学中处理排列的问题。康托展开能够为给定的排列（即一个数列，其中每个数都是不同的）生成一个唯一的自然数，这个数称为康托数（Cantor number）或康托指数。同时，这个方法也可以用于将一个自然数展开为特定的排列。康托展开的过程如下：假设有一个由 $n$ 个不同数字组成的排列 $P = [a_1, a_2, ..., a_n]$，排列中的每个数字 $a_i$ 都是从 1 到 $n$ 的一个整数，且每个数字在排列中只出现一次。康托展开的步骤是：

对于排列中的每个位置 $i$（从 1 到 $n$），计算在该位置之前有多少个数字小于 $a_i$。
将这些小于 $a_i$ 的数字的数量乘以 $(n - i)!$（即从 $n - i + 1$ 到 $n$ 的所有整数的阶乘），并将所有的结果相加。

用数学公式表示，排列 $P$ 的康托数 $C(P)$ 可以这样计算： $C(P) = \sum_{i=1}^{n} (m_i \times (n - i)!) $ 其中 $m_i$ 是在位置 $i$ 之前小于 $a_i$ 的数字的数量。例如，对于排列 $P = [3, 1, 2]$，康托数 $C(P)$ 的计算过程如下：

对于 $a_1 = 3$，在它之前没有比它小的数字，所以 $m_1 = 0$。
对于 $a_2 = 1$，在它之前有一个比它大的数字（3），所以 $m_2 = 0$。
对于 $a_3 = 2$，在它之前有一个比它小的数字（1），所以 $m_3 = 1$。

因此，$ C(P) = 0 \times 2! + 0 \times 1! + 1 \times 0! = 0 + 0 + 1 = 1 $

康托展开的一个应用是在计算排列的字典序中的位置。例如，在上述例子中，排列 $[3, 1, 2]$ 在所有3个数字的排列中是第二个（按照字典序）。康托展开还可以用于证明某些组合恒等式，以及解决与排列相关的计数问题。

逆康托展开¶

对于一个给定的$k$ ，求将自然数$1$ ~$k$ 所有的排列按照字典序从小到大排序后位于第$n$ 的排列。排序从$0$ 开始编号。

由于$n$ 有可能很大，所以现在将给你$k$ 个数，分别为$S_1$ ，$S_2$ ，……，$S_k$ ，规定$n$ 的计算方式为

$n=\sum_{i=1}^k S_i \times (k-i)!$

接下来$T$ 组数据，每组数据的第一行包含$1$ 个数$k$ （$1 \leq k \leq 500000$ ），第二行包含$k$ 个整数，第$i$ 个整数表示$S_i$ （$0 \leq S_i \leq k-i$ ）。

对于输入文件的每组数据，输出一行，包含$k$ 个数，为对应的$1$ ~$n$ 的排列。

我们考虑给出的信息，对于每一组数据，从前往后考虑每一个S_i，其实就是要我们输出当前还存在的数字中第S_i打的数字。权值线段树。

例题 #1 Ryoku 的逆序对¶

Ryoku 有一个正整数 $\{1,2,\cdots,n\}$ 的排列 $A = \{a_i\}$。

她告诉你一个序列 $B = \{b_i\}$，表示对于每个数 $a_i$，对于所有 $j>i$ 有 $b_i$ 个数可以与 $a_i$ 组成逆序对（逆序对的定义是：满足 $i>j$ 且 $a_i < a_j$ 的一组 $(a_i, a_j)$ 称作一对逆序对）。

不幸的是，Ryoku 给你的序列 $B$ 有一些位置污损了，你想知道有多少个可能的排列 $A$ 能符合条件。

请你输出答案并构造一个**字典序最小**的排列 $A$（对于排列 $A = \{a_i\},\ A' = \{a'_i\}$ 若存在某个位置 $i$，使得 $\forall j < i, a_j = a'_j$ 且 $a_i < a'_i$，则 $A$ 的字典序小于 $A'$）。

思路

这里有一个重要的结论，对于序列B，只要不存在b_i>n-i，那么这个B一定可以并且唯一构造出一个合法的序列。

这里可以看看康托展开。

所以现在我们就知道了，一个位置i的-1可以给我们提供的方案数就是乘上n-i+1。其他的b_i提供的方案有且只有一种。

那么第一问就迎刃而解了。现在考虑第二问，我们贪心地构造答案。

假设当前的$b_i=k$，那我们就在所有没有填入的数字中选择地k+1个数字填入。若当前的$b_i=1$，那么我们就选择最小的那个还没有填入的数字填入即可。

为了找到第k个没有添入的数字，我们可以使用线段树，线段树上二分查找即可。

代码时间

注意取模！

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

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

const bool enable_dbg = true;
template <typename T,typename... Args>
void dbg(bool flg,T s,Args... args) {
    if constexpr (enable_dbg){
        cout << s;
        if constexpr (sizeof...(Args))
            dbg(flg,args...);
    }
}

const int N = 1e6 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

int n;
int t[N<<2];
void pushup(int x){
    t[x]=t[x<<1]+t[x<<1|1];
}
void build(int x,int l,int r){
    if(l==r){
        t[x]=1;
        return ;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);

}

void change(int x,int l,int r,int p,int v){
    if(l==r){
        t[x]=v;
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid)change(x<<1,l,mid,p,v);
    else change(x<<1|1,mid+1,r,p,v);
    pushup(x);
}

int query(int x,int l,int r,int p){
    if(l==r)return l;
    int mid=l+r>>1;
    if(t[x<<1]<p)return query(x<<1|1,mid+1,r,p-t[x<<1]);
    return query(x<<1,l,mid,p);
}

int find(int x){
    int loc=query(1,1,n,x);
    change(1,1,n,loc,0);
    return loc;
}

int b[N],a[N];
void solve(){
    n=rd;
    int ans=1;
    for(int i=1;i<=n;i++){
        b[i]=rd;
        if(b[i]>n-i){
            cout<<0<<endl;
            return ;
        }
        if(b[i]==-1)ans*=(n-i+1),ans%=MOD;
    }
    cout<<ans<<endl;
    build(1,1,n);
    for(int i=1;i<=n;i++){
        if(b[i]==-1){
            int q=find(1);
            a[i]=q;
        }else{
            int q=find(b[i]+1);
            a[i]=q;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }

}

signed main() {
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

对于 $10\%$ 的数据，$b_i \neq -1$。对于另外 $10\%$ 的数据，$n \le 10$。对于另外 $10\%$ 的数据，$b_i = -1$。对于另外 $30\%$ 的数据，$n \le 10^3$。对于另外 $30\%$ 的数据，$n \le 10^5$。对于 $100\%$ 的数据，$0< n \le 10^6$，$-1 \le b_i \le n$。