【CF1443E】Long Permutation 题解(排列生成模板)

• 2020 年 11 月 4 日
• 筆記
• Codeforces, 题解

原题链接

题意简介

给定一个长度为 n 的排列 {1,2,3,…,n} 。现有两种操作：

1. 对某个区间 [l,r] 求和
2. 将排列往后推 x 次 (按字典序)

其中 \(n,q \leq 2\times10^5 , x\leq 10^5\) 。

思路分析

乍一看毫无思路。

因为排列变换是毫无疑问的暴力，变换后怎么维护区间和是一个非常玄妙的问题。好像没有什么特殊的维护技巧。

仔细观察数据范围：\(x\leq 10^5 , q\leq 2\times 10^5\)

这意味着 \(\sum x_i \leq 2\times 10^{10}\)

而经过简单的打表观察我们不难发现 \(13! <2\times 10^{10}<14!\)

换句话说，所有的操作过后，会改变的实际上只有最后的 14 个数。

于是问题就简单了，每次更新暴力更改后 14 个数，维护一下前缀和就行了。

那么让我们来考虑如何生成一个排名为 x 的排列。

其实类比如何计算某个排列的排名，反过来就行了。

我的做法是利用树状数组维护比某个数小的数里有几个被选过，然后用二分查找确定当前位置的数字。

详见代码。

代码库

1. 排列生成模板

#include <cstdio>
typedef long long ll;
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
#define Rep(i,a,b) for(REG int i=a;i>=b;i--)
int n,tr[25],A[25]; ll d,fact[25];
inline int lowbit(int x){
    return x&-x;
}
inline int sum(int x){
    REG int ans=0;
    while(x) ans+=tr[x],x-=lowbit(x); 
    return ans;
}
inline void add(int x){
    while(x<=n) tr[x]++,x+=lowbit(x);
}
inline bool check(int x,ll r,int i){
    // x-sum(x) 表示这个数往下的没用过的数的个数
    // x 在 i 位置上的所有情况之和仍不足以达到 d
    return r+(x-sum(x))*fact[n-i]<d;
}
int main(){
    fact[0]=1; rep(i,1,20) fact[i]=fact[i-1]*i;
    while(scanf("%d%lld",&n,&d)==2){
        //tr 用于存储用过的数字
        rep(i,1,n) tr[i]=0;
        REG ll rest=0;
        rep(i,1,n){
            REG int l=1,r=n,mid,ans=0;
            while(l<=r){
                //找到最大的恰不能使序号比 d 大的数字
                mid=(l+r)>>1;
                if(check(mid,rest,i)) ans=mid,l=mid+1;
                else r=mid-1;
            }
            // ans+1 必然没用过，假如用过了，必然会被记为 ans
            A[i]=ans+1; rest+=(ans-sum(ans))*fact[n-i]; add(A[i]);
        }
        rep(i,1,n) printf("%d ",A[i]); putchar('\n');
    }
    return 0;
}

2. 本题题解

#include <cstdio>
#include <cstring>
typedef long long ll;
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
#define Rep(i,a,b) for(REG int i=a;i<=b;i++)
inline char getc(){
    static char buf[1<<14],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline ll scan(){
    REG ll x=0; REG char ch=0;
    while(ch<48) ch=getc();
    while(ch>=48) x=x*10+ch-48,ch=getc();
    return x;
}
inline int max(const int&a,const int&b){
    return a>b?a:b;
}
inline int min(const int&a,const int&b){
    return a<b?a:b;
}
const int N=2e5+5;
//注意初始排列的排名为 1
int n,q,tr[17]; ll sum[N],D=1,fact[17];
inline int lowbit(int x){
    return x&-x;
}
inline int query(int x){
    REG int ans=0;
    while(x) ans+=tr[x],x-=lowbit(x);
    return ans;
}
inline void add(int x){
    //注意这里不是 x<=n
    while(x<=14) tr[x]++,x+=lowbit(x);
}
inline bool check(int x,int i,ll r){
    return r+(x-query(x))*fact[n-i]<D;
}
inline void test(){
    printf("Now:\n");
    rep(i,1,n) printf("%d ",sum[i]-sum[i-1]);
    putchar('\n');
}
int main(){
    n=scan(),q=scan();
    rep(i,1,n) sum[i]=sum[i-1]+i;
    fact[0]=1;
    rep(i,1,14) fact[i]=fact[i-1]*i;
    while(q--){
        REG int opt=scan();
        if(opt==1){
            REG int l=scan(),r=scan();
            printf("%lld\n",sum[r]-sum[l-1]);    
        }else{
            D+=scan(); REG ll rest=0; 
            memset(tr,0,sizeof(tr));
            //只有最后的 14 个数会发生变化
            for(REG int i=max(1,n-13);i<=n;i++){
                REG int l=1,r=min(14,n),mid,ans=0;
                while(l<=r){
                    //找到最大的恰不能使序号比 d 大的数字
                    mid=(l+r)>>1;
                    if(check(mid,i,rest)) l=mid+1,ans=mid;
                    else r=mid-1;
                }
                sum[i]=sum[i-1]+ans+max(1,n-13); 
                rest+=(ans-query(ans))*fact[n-i]; 
                add(ans+1);
            }
            //test();
        }
    }

    return 0;
}

END