codeforces-#681-E

codeforces-#681-E

十一月 10, 2020

E. Long Permutation

  • 题意

给出一个长度为n的排列 :1,2,3,4,5,6…,n (n<2e5)

有q次操作：(q<2e5)

1 l r 询问区间[L,R]内的元素和

2 x 将当前排列的字典序变大 x (x<1e5)

例如 ：

1 2 3 4 5 字典序=1

1 2 3 5 4 字典序=2

1 2 4 3 5 字典序=3

…

对于 1 2 3 4 5 的字典序变大2

则新的排列为 1 2 4 3 5

  • 题解

首先需要意识到 一个长度为n的排列 共有n! 个

这意味着 最差情况下 原排列的字典序会增大 xq次 也就是增大2e10

而只需要15个数 就能产生大于2e10的排列个数

意思是 最差情况下 增大排列的字典序只会改变最后15位的排列

前面的数 仍保持1 2 3 ….. n-15 不变

于是对区间和的询问可以拆分成两段处理

对于[1,n-15] 前缀和处理

对于[n-15,n] 需要使用到一个黑科技

康托展开&逆康托展开

参考博客

为了解决 排列 与其字典序的 双映射问题

即 知道排列可以直接求得其 对应字典序大小 (康托展开)

或已知字典序大小和排列长度n 求出对应排列的问题 (逆康托展开)

X是排列对应字典序

$a_i$表示此排列从右到左第i位在当前未出现的元素(它左侧的数已经出现)中是排第几个

实际可以类比进制转换

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
/*******打出1-n的阶乘表*******/
int f[20];
void jie_cheng(int n)
{
    f[0] = f[1] = 1; // 0的阶乘为1
    for(int i = 2; i <= n; i++) f[i] = f[i - 1] * i;
}
 
/**************康托展开****************/
string str;
int kangtuo()
{
    int ans = 1;  //注意，因为 12345 是算作0开始计算的，最后结果要把12345看作是第一个
    int len = str.length();
    for(int i = 0; i < len; i++){
        int tmp = 0;//用来计数的
 
        for(int j = i + 1; j < len; j++){
            if(str[i] > str[j]) tmp++;
            //计算str[i]是第几大的数，或者说计算有几个比他小的数
        }
 
        ans += tmp * f[len - i - 1];
    }
    return ans;
}

/**************康托逆展开**************/
 
vector<char> vec; //存需要排列的字符
void rev_kangtuo(int k) //输出序号为 k 的字符序列
{
    int n = vec.size(), len = 0;
    string ans = "";
    k--; // 算的时候是按 12345 是第0位
    for(int i = 1; i <= n; i++){
        int t = k / f[n - i]; // 第 i 位需要 第 t + 1 大的数
        k %= f[n - i];        //剩下的几位需要提供的排列数
        ans += vec[t] ; //  vec[t] 就是第 t + 1 大的数
        vec.erase(vec.begin() + t); 
//用过就删了，不用vector用暴力也可以，就是说枚举，然后一个一个的比较大小，并记录有几个没用过的字符且字典序比它小
    }
    cout << ans << '\n';
}

以上是康托展开的具体代码 (算法的具体原理参考链接中的博客)

对于本题 需要对最后15个数进行康托展开 求得对应字典序now

对于每次增加它字典序的操作则对now+=x

用逆康托展开求得对应排列 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
//#define P pair<ll,ll>
const int Max=2e5+5;
const int Mod=998244353;
const int inf=0x3f3f3f3f;


/*

*/
ll sum[Max],p[Max];
ll F[20];
void init(){
    F[0]=1;
    for(int i=1;i<=15;i++)F[i]=F[i-1]*i;
}
ll ConTor(int n,int Mid){
    ll X=1;
    for(int i=Mid+1;i<n;i++){
        ll temp=0;
        for(int j=i+1;j<=n;j++){
            if(p[j]>p[i])continue;
            temp++;
        }
        //cout<<temp<<" "<<F[n-i]<<endl;
        X+=temp*F[n-i];
    }
    return X;
}
bool vis[Max];
void invConTor(int n,int Mid,ll X){
    X--;ll rest=X;
    vector<int>vec;
    for(int i=Mid+1;i<=n;i++){
        vis[i]=0;
        vec.push_back(i);
    }
    for(int i=Mid+1;i<=n;i++){
        int num=rest/F[n-i];
        rest=rest%F[n-i];
        p[i]=vec[num];
        vec.erase(vec.begin()+num);
    }


}
int main(void){
    //Turnoff;
    init();
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)p[i]=i;
    //cout<<ConTor(n,0)<<endl;
    int Mid=max(0,n-15);

    for(int i=1;i<=Mid;i++)sum[i]=sum[i-1]+p[i];
    while(q--){
        int op;cin>>op;
        if(op==1){
            int l,r;cin>>l>>r;
            if(r<=Mid)cout<<sum[r]-sum[l-1]<<endl;
            else if(l<=Mid){
                ll temp=sum[Mid]-sum[l-1];
                for(int i=Mid+1;i<=r;i++)temp+=p[i];
                cout<<temp<<endl;
            }
            else{
                ll temp=0;
                for(int i=l;i<=r;i++)temp+=p[i];
                cout<<temp<<endl;
            }
        }
        else{
            ll x;cin>>x;
            ll now=ConTor(n,Mid);
            //cout<<now<<endl;
            now+=x;
            invConTor(n,Mid,now);
            /*
            for(int i=1;i<=n;i++)cout<<p[i]<<" ";
            cout<<endl;
            */
        }
    }
}