$Solution$:
看到这道题，首先想到排过序的数之间的逆序对都被消掉了。假设当前的已经给 $\le a_k$ 的数排了序。
则对于其它的逆序对分两种：
一个 $\le a_k$ 的数与一个 $>a_k$ 的数组成。对于这个 $>a_k$ 的数，无论 $\le a_k$ 的数怎么排，它贡献的逆序对个数都是一样的，所以不用管。
两个 $>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:$
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
| #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。