题解 P5367 【【模板】康托展开】

一道zz题。

首先我们知道的康托展开，根据给定排列算位次的结论是以下代码：

inline void work_contor(ll *now){
    ll k, l, t, res = 0; 
    for(k = 1; k <= N; k ++){
        t = 0 ; 
        for(l = k + 1; l <= N; l ++)
            if(now[l] < now[k]) t ++ ;
        res += t * Flr[N - k] ; 
    }
    cout << res + 1 << endl ;  
}      

我们试图优化这个东西。我们发现时间复杂度的瓶颈就在于，对于a_i我们不能快速统计a_j < a_i,j > i的二元组<a_i, a_j>的个数。我们发现这就是个逆序对，就可以直接上权值线段树来统计。

不得不说迄今为止这个题的数据还是太弱了。

#include <cstdio>
#include <iostream>
#include <algorithm>

#define rr register 
#define MAXN 1000100
#define Mod 998244353

using namespace std ; int T[MAXN << 1] ;
int query[MAXN], Flr[MAXN], N, K, i, j, q ;

inline void push_up(int rt){
    T[rt] = T[rt << 1] + T[rt << 1 | 1] ; 
}
inline void update(int rt, int l, int r, int p){
    if (l == p && r == p) { T[rt] ++ ; return ; } rr int mid = (l + r) >> 1 ; 
    if (p <= mid) update(rt << 1, l, mid, p) ; else update(rt << 1 | 1, mid + 1, r, p) ; push_up(rt) ; 
}
inline int que(int rt, int l, int r, int ql, int qr){
    if (ql > qr) return 0 ; 
    if (ql <= l && qr >= r) return T[rt] ; rr int mid = (l + r) >> 1, res = 0 ; 
    if (ql <= mid) res += que(rt << 1, l, mid, ql, qr) ; if (qr > mid) res += que(rt << 1 | 1, mid + 1, r, ql, qr) ; return res ; 
}
inline void work_contor(int *now){
    int k, l, t = 0, res = 0; 
    for (k = 1 ; k <= N ; ++ k, t = 0)
        res = (1ll * res + 1ll * (now[k] - que(1, 1, N, 1, now[k] - 1) - 1) * Flr[N - k]) % Mod, update(1, 1, N, now[k]) ;  
    cout << (res + 1) % Mod << endl ;  
}
int main(){
    cin >> N ; Flr[1] = Flr[0] = 1 ; 
    for (i = 2; i <= N ; i ++) Flr[i] = 1ll * Flr[i - 1] * i % Mod ;
    for (j = 1; j <= N ; j ++) scanf("%d", &query[j]) ; work_contor(query) ; return 0 ;
}