BZOJ3925 发表于 2019-10-10 | 阅读数 题意:可修改逆序对开始没理清数据,越打越乱 理清了一波三维偏序,舒服了,自己代码没打错,只是思路错了。 我们先把该删的数删掉那么开始反向添加 比如 所以就三维偏序统计一个数的贡献就好了。 然后反向加就好了 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int N = 5e5 + 10;typedef long long ll;#define lowbit(i) i &(-i)int tr[N << 2], n;void update(int x, int w){ while (x <= n) { tr[x] += w; x += lowbit(x); } return;}int quary(int x){ int sum = 0; while (x) { sum += tr[x]; x -= lowbit(x); } return sum;}struct node{ int pos, v, ti, id;} p[N];int m;ll ans1[N], ans2[N], f[N];bool cmpp(node a, node b){ return a.ti < b.ti;}void cdq(int l, int r){ if (l == r) return; int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r); sort(p + l, p + mid + 1, cmpp); sort(p + 1 + mid, p + r + 1, cmpp); int pl = l, pr = mid + 1; while (pl <= mid) { //cout<<pl<<" "<<pr<<endl; while (pr <= r && p[pl].ti >= p[pr].ti) update(p[pr].pos, 1), pr++; ans1[p[pl].id] += quary(p[pl].pos - 1); pl++; } //分别统计 for (int i = mid + 1; i < pr; i++) update(p[i].pos, -1); pl = l, pr = mid + 1; while (pr <= r) { //cout<<pl<<" "<<pr<<endl; while (pl <= mid && p[pl].ti <= p[pr].ti) update(p[pl].pos, 1), pl++; ans2[p[pr].id] += quary(n) - quary(p[pr].pos); pr++; } for (int i = l; i < pl; i++) update(p[i].pos, -1);}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); p[x].pos = i; p[x].v = x; } for (int i = 1; i <= m; i++) { int x; scanf("%d", &x); p[x].ti = m - i + 1; p[x].id = i; } cdq(1, n); f[m + 1] = ans1[0] + ans2[0]; f[m + 1] /= 2; // for(int i=0;i<=m;i++) // cout<<ans1[i]<<' '<<ans2[i]<<endl; for (int i = m; i >= 1; i--) f[i] = f[i + 1] + ans1[i] + ans2[i]; for (int i = 1; i <= m; i++) printf("%lld\n", f[i]);}