自动搬运

查看原文

来自洛谷，原作者为

	Stinger **

搬运于2025-08-24 21:45:49，当前版本为作者最后更新于2021-01-17 20:55:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$Solution$:

看到这道题，首先想到排过序的数之间的逆序对都被消掉了。假设当前的已经给 $\le a_k$ 的数排了序。

则对于其它的逆序对分两种：

1. 一个 $\le a_k$ 的数与一个 $>a_k$ 的数组成。对于这个 $>a_k$ 的数，无论$\le a_k$ 的数怎么排，它贡献的逆序对个数都是一样的，所以不用管。

2. 两个 $>a_k$ 的数组成。这种明显个数不变也不用管。

对于一个操作 $a_k$，如果之前存在一个操作 $a_{k^{\prime}}$ 使得 $a_{k^{\prime}}\ge a_k$ ，则这个操作不用考虑，直接输出上一次询问的答案。

对于一个要考虑的操作 $k$。排除了上面两种逆序对，我们就要在总的逆序对个数中减去所有 $\le a_k$ 的数构成的逆序对。预处理 $\le i$ 的数之间产生的逆序对记为 $s_i$。树状数组预处理出来即可。

至于这个预处理的过程，简要说一下（这也是我想得最久的地方）：从右往左扫描数组，遇到一个数 $a_i$，$s_{a_i} +=$ 目前遇到过的比 $a_i$ 小的数。原理比较明显。

然后对 $s_i$ 做个前缀和。

$Code:$

#include <cstdio>
#include <algorithm>
#define int long long

struct node {
	int id, v;
	inline bool operator < (const node x) const {return v < x.v;}
} b[300005];
inline bool operator < (const int x, const node y) {return x < y.v;}
int a[300005], c[300005], s[300005], n, N;
inline void update(const int x) {
	for (int i(x); i <= n; i += (i & ~i + 1)) ++ c[i];
}
inline int query(const int x) {
	int sum(0);
	for (int i(x); i; i -= (i & ~i + 1)) sum += c[i];
	return sum;
}

signed main() {
	int m, last(0);
	scanf("%lld%lld", &n, &m);
	for (int i(1); i <= n; ++ i) scanf("%lld", &b[i].v), b[i].id = i;
	std::sort(b + 1, b + n + 1);
	a[b[1].id] = 1;
	for (int i(2); i <= n; ++ i)
	a[b[i].id] = (b[i].v != b[i - 1].v) + a[b[i - 1].id];
	for (int i(n); i >= 1; -- i)
		s[a[i]] += query(a[i]), update(a[i]);
	N = a[b[n].id];
	for (int i(2); i <= N; ++ i) s[i] += s[i - 1];
	printf("%lld\n", s[N]);
	a[0] = -0x3fffffff;
	while (m --) {
		int k;
		scanf("%lld", &k);
		if (a[k] < a[last]) k = last;
		last = k;
		printf("%lld\n", s[N] - s[a[k]]);
	}
	return 0;
}

逆序对很玄，讨论区有说，另外我让小粉兔大佬换数据了不过暂时还没换。相信粉兔不会咕多久qwq。