题解 P5367 【【模板】康托展开】
皎月半洒花
2019-05-13 17:01:13
一道zz题。
首先我们知道的康托展开，根据给定排列算位次的结论是以下代码：
```cpp
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>$的个数。我们发现这就是个逆序对，就可以直接上权值线段树来统计。
不得不说迄今为止这个题的数据还是太弱了。
```cpp
#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 ;
}
```