题意简介

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

对某个区间 [l,r] 求和
将排列往后推 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;

}

巴特西

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

题意简介

思路分析

代码库

1. 排列生成模板

2. 本题题解

END

最新文章

热门文章