P5367 【模板】康托展开 线段树题解

· · 题解

P5367 【模板】康托展开

发现这题各位大佬都是用的树状数组，然而苯宝宝比较笨，不会树状数组，于是苯宝宝就来水一篇线段树的题解~（第一次发题解，写的不好求指出~）（也求大家支持一下下啦~）

1.康托展开的定义和式子

（各位大佬都是跳过这一段的吧？）

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。（from 百度）

式子：百度百科上的式子貌似是错的

X = a_{1}(n-1)!+a_{2}(n-2)!+\cdots+a_{n}\cdot0!

其中 a_{i} 指的是在当前 未出现 的数字中有几个比已知排列的第 i 位小，通过这个式子可以求出在全排列中有多少排列在已知排列的前面。举个栗子：

排列：1,4,3,2,5

第一位：1 在 1,2,3,4,5 中排第 1 个 → 0\times4!

第二位：4 在 2,3,4,5 中排第 3 个 → 2\times3!

第三位：3 在 2,3,5 中排第 2 个 → 1\times2!

第四位：2 在 2,5 中排第 1 个 → 0\times1!

第五位：5 在 5 中排第 1 个 → 0\times0!

所以 X=0\times4!+2\times3!+1\times2!+0\times1!+0\times0!=14

所以，如果输出 14 你就光荣的 WA 啦！

这个 X 只是这个排列之前的排列数，而我们要求这个排列的位置，所以 ans=X+1=15。

2.大致思路

根据式子，我们可以得出，我们需要求两样东西：1 至 n 的阶乘，每个位置上的数在未出现的数中的排序。

前者可以用一个前缀积数组解决：（类似前缀和）不会前缀和的出门左转

int fact[MAXN]={1};//初始化0的阶乘为1
for(int i=1; i<=N; i++) {
    fact[i]=(fact[i-1]*i)%MOD;
}

后者我们可以很显然的想到暴力枚举，时间复杂度为 O(n^{2})。回头一看题面，对于100\%数据，1 \le N\le 1,000,000。所以，这么做是妥妥的 TLE 。我们在前面的遍历上浪费了大量时间。其实，我们只需要维护前面数的个数的总和就行了。因此，我们可以想到用来维护区间和的利器——线段树！

3.线段树解法

不会线段树的戳这里

这题用线段树的基本思路就是将线段树的各个叶子节点初始化为 1，然后从排列的第一个数开始向后，每次将线段树的第 i 位设置为 0，再用线段树求出 [1,i-1] 的区间和，即为未出现的数中比 i 小的数的个数。

苯宝宝作为一个刚学线段树没多久的菜鸡，在努力手打复制线段树的时候遇到了各种各样的问题，其中最主要的是空间不够：（这种时候想到楼上大佬们树状数组 O(n) 空间，心中颇有点想放弃的冲动）

苯宝宝一开始用的是结构体存线段树：(显然是复制的)

struct Tree {
    long long Left,Right,Num,Lazy;
} tree[4*MAXN];

于是来了个干干净净的 MLE

回过头来细细分析：我们需要线段树的那么多功能吗？

答案很显然，不需要。

于是接下来就是对又长又烦人的线段树加以阉割再阉割

首先，由于这题我们需要单点修改，这是个绝对标记（相对标记和绝对标记的概念都会吧），因此Lazy标记就没有作用啦！然后是Left和Right，为了节省空间，把它们转移到代码中去 （这让代码显得更丑但是没办法） 这样，我们就只需要一个Num数组来存储~ （苯宝宝还曾作死把long long换成了int导致 WA ）

接下来就是依旧又长又烦人的线段树AC代码：（在被一个邻座的比苯宝宝小但是比苯宝宝强太多的大佬@♗Wendigo♝吐槽过后把很多普通运算改成了位运算）（k<<1 = k\times2 ; k<<1|1 = k\times2+1）

#include<bits/stdc++.h>
#define MAXN 1000010
#define MOD 998244353
#define LL long long//偷懒神技
using namespace std;

inline LL read() {//依旧是复制的快读
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

LL N,ans,temp;
LL Num[4*MAXN];//某位大佬曾告诉苯宝宝开四倍空间比较好（虽然据说两倍够用）
LL fact[MAXN]= {1};

inline void PushUp(LL k) {
    Num[k]=(Num[k<<1]+Num[k<<1|1])%MOD;//别忘了MOD！
    return;//return 是个好习惯
}

inline void Build(LL l,LL r,LL k) {
    if(l==r) {
        Num[k]=1;
        return;
    }
    LL mid=(l+r)>>1;
    Build(l,mid,k<<1);
    Build(mid+1,r,k<<1|1);
    PushUp(k);
    return;
}

inline void PointSet0(LL k,LL l,LL r,LL p) {//把p设定为0
    if(l==r) {
        Num[k]=0;
        return;
    }
    LL mid=(l+r)>>1;
    if(p<=mid) {
        PointSet0(k<<1,l,mid,p);
    } else {
        PointSet0(k<<1|1,mid+1,r,p);
    }
    PushUp(k);
    return;
}

inline LL QuerySegment(LL k,LL l,LL r,LL ql,LL qr) {//查询[ql,qr]区间和
    if(ql>qr) {//不加这个会出问题，，苯宝宝栽过一次
        return 0;
    }
    if(ql==l&&qr==r) {
        return Num[k];
    }
    LL mid=(l+r)>>1;
    if(qr<=mid) {
        return QuerySegment(k<<1,l,mid,ql,qr);
    } else if(ql>mid) {
        return QuerySegment(k<<1|1,mid+1,r,ql,qr);
    } else {
        return (QuerySegment(k<<1,l,mid,ql,mid)+QuerySegment(k<<1|1,mid+1,r,mid+1,qr))%MOD;//别忘了MOD！
    }
}

int main() {
    N=read();
    Build(1,N,1);
    for(int i=1; i<=N; i++) {
        fact[i]=(fact[i-1]*i)%MOD;
    }
    for(int i=1; i<=N; i++) {
        temp=read();
        PointSet0(1,1,N,temp);
        ans=(ans+(QuerySegment(1,1,N,1,temp-1)*fact[N-i])%MOD)%MOD;
    }
    printf("%lld\n",ans+1);//别忘了+1！
    return 0;
}

[某个强者]曾说苯宝宝的码风极其丑