自动搬运

查看原文

来自洛谷，原作者为

	_louhc 已故 o（x（工）x）o

搬运于2025-08-24 22:10:04，当前版本为作者最后更新于2019-05-18 22:30:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

康托展开真是个神奇的东西。
除了本题用于求某排列的排名外，康托展开一般用于哈希，不过我也没做到过这样的哈希题。

康托展开

先给你柿子。

其中$A[i]$代表$\sum_{j=i}^{n}[a[j] < a[i]]$
怎么来理解这个柿子呢？想象构造出字典序比当前排列小的有几个排列
枚举到$i$表示 1到i-1和原来的排列一样，i位肯定不一样，之后咋样都行。
既然到i位不一样，那么字典序大小其实就是取决于i位。很明显，第i位肯定要小于a[i]。然后只要把i后面小于a[i]的数交换到i位，后面随便排就行了。
很明显，这样枚举可以做到不重不漏。因为要求的是排名，所以ans+=1。
当然要用树状数组优化一下，复杂度是O(nlgn)的。

双语代码（滑稽

写Pascal就是为了卡常数,加O2秒杀C++)

C++98/11/14/17

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define rgt register
#define mod 998244353

int N, a[MAXN], fac, c[MAXN], ans;
char *p;

inline void read( rgt int &x ){
	x = 0; while( !isdigit(*p) ) ++p;
	while( isdigit(*p) ) x = x * 10 + ( *p & 15 ), ++p;
}

int main(){
	scanf( "%d", &N ), fac = 1;
	p = new char[N * 8 + 100],
	fread( p, 1, N * 8 + 100, stdin );
	for ( rgt int i = N; i; --i ) read(a[i]);
	for ( rgt int i = 1, s, j; i <= N; ++i ){
		for ( s = 0, j = a[i]; j; j -= j & -j ) s += c[j];
		ans = ( ans + 1ll * fac * s ) % mod, fac = 1ll * fac * i % mod;
		for ( j = a[i]; j <= N; j += j & -j ) ++c[j];
	} printf( "%d\n", ans + 1 );
	return 0;
}

Pascal

var
n, fac, s, ans, i, j:longint;
a, c:array[1..1000000] of longint;
begin
    read(n); fac := 1; ans := 0;
    for i := n downto 1 do
    begin
        read(a[i]);
        c[i] := 0;
    end;
    for i := 1 to n do
    begin
        j := a[i]; s := 0;
        while j > 0 do
        begin
            s := s + c[j];
            j := j - ( j and -j ); 
        end;
        ans := ( QWORD(ans) + QWORD(fac) * QWORD(s) ) mod 998244353;
        fac := QWORD(fac) * QWORD(i) mod 998244353;
        j := a[i];
        while j <= n do
        begin
            c[j] := c[j] + 1;
            j := j + ( j and -j );
        end;
    end;
    writeln((ans + 1) mod 998244353);
end.

逆康托展开

类似于进制转换，不断 % (n-i)!, /(n-1)!就可以得到A数组，然后就可以还原出原排列。

Update on 2019.7.23
昨天刚刚集训回来，于是就来填坑了

例题
这题十分好心地为我们省去了求出A数组的过程（否则要高精度除法？
问题说白了就是在每一个[i,n]区间内求K大值。可以使用权值线段树+二分来解决这一问题。这应该比较基础，所以看代码吧qaq。

代码

没怎么卡常数，本来想搞zkw线段树非递归减小常数，但是懒。。。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50005

int T, N, tr[MAXN << 2];

void Build( int c, int l, int r ){ //建树
	if ( l == r ) return tr[c] = 1, void();
	int mid((l + r) >> 1), ls(c << 1), rs(c << 1 | 1);
	Build( ls, l, mid ), Build( rs, mid + 1, r ),
	tr[c] = tr[ls] + tr[rs];
}

int Get( int c, int l, int r, int k ){ //找到k大值的同时删除k大值
	--tr[c]; if ( l == r ) return l;
	int mid((l + r) >> 1), ls(c << 1), rs(ls | 1);
	if ( tr[ls] < k ) return Get( rs, mid + 1, r, k - tr[ls] );//线段树上二分找到k大值
	return Get( ls, l, mid, k );
}

int main(){
	scanf( "%d", &T );
	while( T-- ){
		scanf( "%d", &N ), Build( 1, 1, N );
		for ( int i = 1, s; i <= N; ++i )
			scanf( "%d", &s ), printf( "%d%c", Get(1, 1, N, s + 1), "\n "[i < N] );
	} return 0;
}