让我们考虑这样一件事情,考试出原题是多么有趣啊。
描述:
给定一个长为 \(n\) 的序列,每次将 \(a\) 小于等于 \(k\) 位置的所有人提取出来,按照身高从小到大排序,依次插入对应的位置,每次操作后求其 \(a\) 的逆序对。
思路:
发现如果 \(k_1\ge k_2\) ,那么 \(k_2\) 对 \(k_1\) 没有影响,也就是每次操作对答案有影响的 \(k\) 是递增的。
对于有效的 \(k\) ,发现不需要考虑前面的操作,因为以前的操作对当前答案没有影响。
考虑一次操作,大于 \(k\) 的集合内部逆序对数不变,排序小于等于 \(k\) 的集合 对 大于 \(k\) 的集合 和 小于等于 \(k\) 的集合 之间 的逆序对数不变,唯一变化的是小于等于 \(k\) 的集合内部逆序对数改变。
考虑预处理出小于等于 \(k\) 的逆序对数,按照 \(a\) 从小往大加入元素,用树状数组维护在加入位置后面的元素个数即可。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#define LL long long
#define DB double
#define PR pair <LL, int>
#define MK make_pair
#define RI register int
#define Low(x) (x & (-x))
using namespace std;
const int kN = 3e5 + 5;
struct Node {
int x, pos;
bool operator < (const Node &K) const {
if (x != K.x)
return x < K.x;
return pos < K.pos;
}
}p[kN];
int n, m;
int a[kN], b[kN], len;
LL ans, num[kN];
bool v[kN];
struct BIT {
LL c[kN];
void Add(int x, int k, bool lim) {
if (!lim) {
for (x; x <= len; x += Low(x)) c[x] += k;
}
else {
for (x; x <= n; x += Low(x)) c[x] += k;
}
}
LL Ask(int x) {
LL res = 0;
for (x; x; x -= Low(x)) res += c[x];
return res;
}
}d, d2;
void Solve() {
for (int i = 1; i <= n; ++i) {
ans += d.Ask(len) - d.Ask(a[i]);
d.Add(a[i], 1, 0);
}
printf("%lld\n", ans);
for (int i = 1; i <= n; ++i) {
p[i] = (Node) {a[i], i};
}
sort(p + 1, p + 1 + n);
LL res = 0;
for (int i = 1; i <= n; ++i) {
res += d2.Ask(n) - d2.Ask(p[i].pos);
d2.Add(p[i].pos, 1, 1);
num[p[i].x] = res;
}
LL last = ans;
for (int i = 1, j = 0; i <= m; ++i) {
int k; scanf("%d", &k);
if (v[k]) {
printf("%lld\n", last);
continue;
}
while (j < n && p[j + 1].x <= a[k]) {//
j++;
v[p[j].pos] = 1;
}
printf("%lld\n", ans - num[a[k]]);
last = ans - num[a[k]];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + 1 + n);
len = unique(b + 1, b + 1 + n) - (b + 1);
for (int i = 1; i <= n; ++i) {
a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
}
Solve();
return 0;
}