先上个模板题

[USACO11FEB] Cow Line

https://www.luogu.com.cn/problem/P3014

题意：康托展开模板，给定排列问第几个，给定位置问排列。

可以暴力，但没必要。

注意一下逆康托展开的二分，要找的是满足 query(x) - 1 >= tmp 的最小的数，那么这个数的a值一定是 1，因为再往左a值就-1了，如果右边的数a值为 0，那么 query(x+1) - 1和 query(x) - 1 相同，也满足条件。

树状数组。O(q nlog⁡nlog⁡n)O(q\ n\log n\log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int a[N]; ll P[N];
int sum[N];
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
	for (int i = p; i <= n; i += lowbit(i))
		sum[i] += x;
}
int query(int r) {
	if (r == 0)return 0;
	int ans = 0;
	for (int i = r; i > 0; i -= lowbit(i))
		ans += sum[i];
	return ans;
}
ll cal() {
	ll ans = 1;
	for (int i = n; i >= 1; i--) {
		ans += P[i - 1] * query(a[n - i + 1] - 1);
		add(a[n - i + 1], -1);
	}
	return ans;
}
void sol(ll x) {
	x--;
	for (int i = n; i >= 1; i--) {
		ll tmp = x / P[i - 1];
		int L = 1, R = n;
		while (L < R) {
			int mid = (L + R) / 2;
			if (query(mid) - 1 >= tmp)R = mid;
			else L = mid + 1;
		}
		a[n - i + 1] = L;
		add(L, -1);
		x %= P[i - 1];
	}
}
int main() {
	cin >> n >> m;
	P[0] = 1ll;
	for (int i = 1; i <= n; i++)P[i] = P[i - 1] * i;
	while (m--) {
		char op;
		scanf(" %c", &op);
		fill(sum, sum + n + 1, 0);
		for (int i = 1; i <= n; i++)add(i, 1);
		if (op == 'Q') {
			for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
			printf("%lld\n", cal());
		}
		else {
			ll x;
			scanf("%lld", &x);
			sol(x);
			for (int i = 1; i <= n; i++)printf("%d%s", a[i], i == n ? "\n" : " ");
		}
	}
	return 0;
}

 

D. Misha and Permutations Summation

http://codeforces.com/problemset/problem/501/D

题意：定义两个排列的加法：（第一个排列的位置+第二个排列的位置）mod n！，得到答案排列的位置，求出答案排列。 (1 ≤ n ≤ 200 000)

如果n小的话可以直接康托展开求出位置，再逆展开得到排列，但n这么大显然不行，n的阶乘都表示不了。

但是排列数的性质和进制数很类似，可以发现，n⋅n!=(n−1)⋅(n−1)!+(n−2)⋅(n−2)!+⋯+2⋅2!+1⋅1!+1n\cdot n!=(n-1)\cdot (n-1)!+(n-2)\cdot (n-2)!+\cdots +2\cdot 2!+1\cdot 1!+1

所以就可以当成进制一样加法进位，最后由于 modmod n!n!，所以最高位就没有了。

再考虑逆康托展开的过程，也就是把一个数拆成这个进制表示的过程，而现在已经得到了每一位的值，反倒不需要再自己拆了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int ta[N], tb[N], a[N], b[N], s[N], ans[N];
int sum[N];
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
	for (int i = p; i <= n; i += lowbit(i))
		sum[i] += x;
}
int query(int r) {
	int ans = 0;
	for (int i = r; i > 0; i -= lowbit(i))
		ans += sum[i];
	return ans;
}
void pre(int* a, int* ans) {
	fill(sum + 1, sum + n + 1, 0);
	for (int i = 1; i <= n; i++)add(i, 1);
	for (int i = 1; i <= n; i++) {
		ans[i] = query(a[i] - 1);
		add(a[i], -1);
	}
}
void solve() {
	fill(sum + 1, sum + n + 1, 0);
	for (int i = 1; i <= n; i++)add(i, 1);
	for (int i = 1; i <= n; i++) {
		int L = 1, R = n;
		while (L < R) {
			int mid = (L + R) / 2;
			if (query(mid) - 1 >= s[i])R = mid;
			else L = mid + 1;
		}
		ans[i] = L;
		add(L, -1);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &ta[i]), ta[i]++;
	for (int i = 1; i <= n; i++)scanf("%d", &tb[i]), tb[i]++;
	pre(ta, a);
	pre(tb, b);
	for (int i = n; i >= 1; i--) {
		s[i] = (a[i] + b[i]) % (n - i + 1);
		a[i - 1] += (a[i] + b[i]) / (n - i + 1);
	}
	solve();
	for (int i = 1; i <= n; i++)printf("%d%s", ans[i] - 1, i == n ? "\n" : " ");
	return 0;
}