banner

原题链接

https://www.luogu.com.cn/problem/P3014

解题思路

康托展开（使用树状数组优化）与逆康托展开。

在康托展开时，需要计算每一位数字在它和它以后的所有数字中是第几大的数，在这里我使用了树状数组对算法的时间复杂度进行了优化。

我们设add(x,y)是将x加上y，ask(x)是查询x的前缀和。在预处理时，我们对从1到n的每一个i都分别add(i,1),假设我们当前算到了第i位数a[i]，首先我们add(a[i],-1),这个操作就相当于把a[i]划掉，而在第i位之前出现过的数都已经被我们提前划掉了。那么ask(a[i])即为在第i位之后出现的比a[i]小的数的总个数（即：还未被划掉的比a[i]小的数的总个数）。这样，我们就巧妙地利用了树状数组的性质对康托展开进行了优化。在数据较大时，这种优化作用是极为显著的。

最后提醒一下：一定要开long long！

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
ll n,k,t2,ans,fact[21],tree[21];
bool vis[21];
char t1;
void add(ll x,ll y)
{
  for(;x<=n;x+=x&-x)tree[x]+=y;
}
ll ask(ll x)
{
  ll res=0;
  for(;x;x-=x&-x)res+=tree[x];
  return res;
}
int main()
{
  scanf("%lld%lld",&n,&k);
  fact[0]=1;
  for(ll i=1;i<n;i++)fact[i]=fact[i-1]*i;//递推求阶乘
  while(k--)
    {
      cin>>t1;
      memset(tree,0,sizeof(tree));
      memset(vis,0,sizeof(vis));
      for(ll i=1;i<=n;i++)add(i,1);//预处理树状数组
      switch(t1)
    {
    case 'Q'://康托展开（树状数组优化）
      ans=0;
      for(ll i=1;i<=n;i++)
        {
          scanf("%lld",&t2);
          add(t2,-1);//划掉这个数
          ans+=ask(t2)*fact[n-i];//运用树状数组求这位数字在它和它以后的所有数字中是第几大的数
        }
      printf("%lld\n",ans+1);//记得求出来的结果要加1
      break;
    case 'P'://逆康托展开
      scanf("%lld",&t2);
      t2--;
      for(ll i=1;i<=n;i++)
        {
          ll temp=t2/fact[n-i];
          for(ll j=1;j<=n;j++)
        {
          if(vis[j])continue;
          if(!temp)
            {
              printf("%lld ",j);
              vis[j]=1;
              break;
            }
          temp--;
        }
          t2%=fact[n-i];
        }
      printf("\n");
    }
    }
  return 0;
}