首页 > 代码库 > CF501D Misha and Permutations Summation(康托展开)

CF501D Misha and Permutations Summation(康托展开)

以前写康托展开都是直接O(n^2),碰到了一定要nlogn的,存个代码。

#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define maxn 210000int 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(康托展开)