CF501D Misha and Permutations Summation(康托展开)

将一个排列映射到一个数的方法就叫做康托展开。它的具体做法是这样的，对于一个给定的排列｛ai｝（i=1,2,3...n），对于每个ai求有多少个aj,使得j>i且ai>aj，简单来说就是求ai后面有多少数比ai小，假设我们求出来了这样的排列的一个对应数组{bi},其中bi就是ai后面有多少个数比它小。那么这个排列对应的康托展开即为∑bi*(n-i)!.

ai={1 3 5 4 2}

bi={0 1 2 1 0} 对应的排列数 0*4!+1*3!+2*2!+1*1!+0*0!.

bi可以通过树状数组在O(nlogn)里得到。

至于逆康托展开，就是已知bi，反求出ai,即知道了{0 1 2 1 0}.

做法也是类似的，我们看第一个数是0，表示后面有0个比它小的数，那么它必然是1.然后看第二个数是1，表示这个数在除去1 后面有1个比它小的数，那么这个数就是3，然后2，表示这个数后面在除去1，3，之后有2个比它小的数，所以它是5，以此往下。

一个O(nlogn)的想法是这样的，建立一棵平衡树，把1～n都插进去，每次查找第（bi＋1）大的数，即为第i个数，然后把这个数删掉，以此往复。

但手写一个支持找第k大的平衡树比较慢，另外一个想法是在bit里把每个数都置1，然后二分出第一个使得前缀和为bi+1的数，这样做的复杂度就变成了O(nlog^2n).

#pragma warning(disable:4996)

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

#define maxn 210000

int bit[maxn];

int n;

void upd(int i)

{

	while (i <= n){

		bit[i] += 1;

		i += i&(-i);

	}

}

void dec(int i)

{

	while (i <= n){

		bit[i] -= 1;

		i += i&(-i);

	}

}

int cal(int i)

{

	int ret = 0;

	while (i > 0){

		ret += bit[i];

		i -= i&(-i);

	}

	return ret;

}

int solve(int x)

{

	int l = 1, r = n+1;

	while (l < r)

	{

		int mid = (l + r) >> 1;

		int tx = cal(mid);

		if (tx < x) l = mid + 1;

		else r = mid;

	}

	return l;

}

int a[maxn];

int b[maxn];

int c[maxn];

int va[maxn];

int vb[maxn];

int vc[maxn];

int main()

{

	while (cin >> n)

	{

		for (int i = 0; i < n; ++i){

			scanf("%d", a + i); a[i]++;

		}

		for (int i = 0; i < n; ++i){

			scanf("%d", b + i); b[i]++;

		}

		memset(bit, 0, sizeof(bit));

		for (int i = n - 1; i >= 0; --i){

			va[i] = cal(a[i]);

			upd(a[i]);

		}

		memset(bit, 0, sizeof(bit));

		for (int i = n - 1; i >= 0; --i){

			vb[i] = cal(b[i]);

			upd(b[i]);

		}

		reverse(va, va + n);

		reverse(vb, vb + n);

		memset(vc, 0, sizeof(vc));

		int carry = 0;

		for (int i = 1; i < n; ++i){

			vc[i] = (carry + va[i] + vb[i]) % (i + 1);

			carry = (carry + va[i] + vb[i]) / (i + 1);

		}

		reverse(vc, vc + n);

		memset(bit, 0, sizeof(bit));

		for (int i = 1; i <= n; ++i){

			upd(i);

		}

		for (int i = 0; i < n; ++i){

			c[i] = solve(vc[i]+1);

			dec(c[i]);

		}

		for (int i = 0; i < n; ++i){

			if (i) printf(" ");

			printf("%d", c[i]-1);

		}

		puts("");

	}

	return 0;

}

巴特西

CF501D Misha and Permutations Summation(康托展开)

最新文章

热门文章