自动搬运

查看原文

来自洛谷，原作者为

	Eason_cyx Play like you never did before?

搬运于2025-08-24 23:06:23，当前版本为作者最后更新于2024-11-24 20:54:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

无聊缝合怪题。就是俩板子合一起了。

你会发现这些“随机打乱”和所谓的字典序，都是按照相对大小排序的。那么每个数具体是多少其实不重要，那么直接离散化。离散化完了之后就转换成了 【模板】康托展开，不会的可以去学习一下，此处直接贺板子即可。

时间复杂度瓶颈在离散化的排序和康托展开的树状数组。总时间复杂度 $O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e9 + 7;
long long jc[1000005], tree[1000005], rk[1000005], n, ans = 1;
struct node { long long id,x;
	bool operator < (const node& y) const { return x < y.x; }
} a[1000005]; long long lowbit(long long x) { return x & (-x); }
long long sum(long long x) {
	long long ans = 0; while(x) ans += tree[x] % Mod, x -= lowbit(x);
	return ans % Mod;
} void add(long long x,long long k) {
	while(x <= n) tree[x] += k, x += lowbit(x);
} int main() { cin >> n; jc[0] = 1;
	for(int i = 1;i <= n;i++) cin >> a[i].x, a[i].id = i;
	sort(a+1,a+n+1); for(int i = 1;i <= n;i++) rk[a[i].id] = i;
	for(int i = 1;i <= n;i++) jc[i] = jc[i-1] * i % Mod, jc[i] %= Mod;
	for(int i = 1;i <= n;i++) add(i,1); for(int i = 1;i <= n;i++) {
		ans += ((sum(rk[i]) - 1) * jc[n-i] % Mod) % Mod; add(rk[i],-1);
	} cout << ans % Mod << endl;
	return 0;
}