2025/10/20
AT_arc181_d Prefix Bubble Sort
很显然的有每一次交换都会恰好减少一个逆序对，于是题目转化为每次会产生多少次交换。
那么考虑如何统计交换次数
- 发现当前缀 max 变化时不会产生答案，但是这个折线非常困难维护，不考虑这种做法
- 考虑每个数往后交换多少次是难的，那么考虑有多少个数会往前交换。可以发现当前面有数大于这个数时，这个数一定会产生一次交换，那么直接统计有多少个数前面有大于它的数即可。由于题目限制了 \(A_i\) 单调不减，直接线段树简单维护即可
没有想到可以换一种贡献方式，老是在一棵树上吊死。
Code
#include <iostream>using namespace std;
using ll = long long;const int kN = 2e5 + 1;int n, m, a[kN];
ll ans;
struct BIT {int tr[kN];void Update(int x, int k) {for (; x < kN; x += x & -x)tr[x] += k;}int Query(int x) {int res = 0;for (; x; x -= x & -x)res += tr[x];return res;}
} Bit;
struct Point {int mn, cnt, tag;
} tr[kN << 2];void Func(int x, int k) {tr[x].mn += k, tr[x].tag += k;
}
void Pushdown(int x) {Func(x * 2, tr[x].tag), Func(x * 2 + 1, tr[x].tag), tr[x].tag = 0;
}
void Find(int x, int l, int r) {if (tr[x].mn > 0)return;if (l == r)return tr[x].mn = tr[x].tag = 1e9, tr[x].cnt = 0, void();Pushdown(x);int m = (l + r) / 2;Find(x * 2, l, m), Find(x * 2 + 1, m + 1, r);tr[x].mn = min(tr[x * 2].mn, tr[x * 2 + 1].mn), tr[x].cnt = tr[x * 2].cnt + tr[x * 2 + 1].cnt;
}
void Update(int nl, int nr, int x = 1, int l = 1, int r = n) {if (nl <= l && r <= nr)return Func(x, -1), Find(x, l, r);Pushdown(x);int m = (l + r) / 2;if (nl <= m)Update(nl, nr, x * 2, l, m);if (nr > m)Update(nl, nr, x * 2 + 1, m + 1, r);tr[x].mn = min(tr[x * 2].mn, tr[x * 2 + 1].mn), tr[x].cnt = tr[x * 2].cnt + tr[x * 2 + 1].cnt;
}
void Build(int x = 1, int l = 1, int r = n) {if (l == r)return tr[x].cnt = a[l] > 0, tr[x].mn = a[l] ? a[l] : 1e9, void();int m = (l + r) / 2;Build(x * 2, l, m), Build(x * 2 + 1, m + 1, r);tr[x].mn = min(tr[x * 2].mn, tr[x * 2 + 1].mn), tr[x].cnt = tr[x * 2].cnt + tr[x * 2 + 1].cnt;
}
int Query(int nl, int nr, int x = 1, int l = 1, int r = n) {if (nl <= l && r <= nr)return tr[x].cnt;Pushdown(x);int m = (l + r) / 2, res = 0;if (nl <= m)res = Query(nl, nr, x * 2, l, m);if (nr > m)res += Query(nl, nr, x * 2 + 1, m + 1, r);return res;
}int main() {
#ifndef ONLINE_JUDGEfreopen("in", "r", stdin);freopen("out", "w", stdout);
#endifcin.tie(0)->sync_with_stdio(0);cin >> n;for (int i = 1, x; i <= n; i++) {cin >> x;a[i] = Bit.Query(n - x + 1), Bit.Update(n - x + 1, 1), ans += a[i];}Build();cin >> m;for (int i = 1, x; i <= m; i++) {cin >> x;ans -= Query(1, x), Update(1, x);cout << ans << '\n';}return 0;
}