扯

好像距离上次写题解已经有百年之久了……来更新个吧。

我吹爆 gyh！

题意

给定一个 \(1\sim n\) 的排列，按照题目给定顺序依次删除 \(m\) 个数。

求每次删数前整个序列中的逆序对数。

\(1\le n\le 10^5,1\le m\le 5\times 10^4\)

思路

cdq 分治

将询问离线，并反转序列，将序列删数改为插入。

原问题就转化为了有一个序列 \(a\)，每次添加一个数 \(a_i\)，并求序列的逆序对数。

对于一个数 \(a_i\)，设其被加入的时间为 \(t_i\)。

假设现在有两个数 \((a_i,a_j)\)，那么两个数能够形成逆序对的条件是：

\(i<j,a_i>a_j,t_i>t_j\) 或 \(i>j,a_i < a_j,t_i>t_j\)。

那么这样就转化成了两个三维偏序问题，用 cdq 实现即可。可以分两个 cdq 分别处理两种情况，也可以用一个 cdq 直接处理两种情况。

还原总逆序对数后记得要逆序输出，因为 \(t_i\) 是倒序处理的。

Luckyblock 教我树状数组懒惰删除秘诀！

代码

#include <bits/stdc++.h>
#define ll long long
#define A 100010
using namespace std;

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

ll ans[A], t[A];
struct node { int x, y, z; } a[A], b[A];
int n, m, val[A], tim[A], del[A], pos[A], Time;

inline int lowbit(int x) { return (x & -x); }
bool cmp(node fi, node se) { return fi.x < se.x; }
bool cmp1(node fi, node se) { return fi.y < se.y; }
bool cmp2(node fi, node se) { return fi.y > se.y; }

void add(int x, int val) {
  for ( ; x <= n; x += lowbit(x)) {
    if (tim[x] < Time) t[x] = 0, tim[x] = Time;
    t[x] += val;
  }
}

int query(int x, int res = 0) {
  for ( ; x; x -= lowbit(x)) {
    if (tim[x] < Time) t[x] = 0, tim[x] = Time; 
    res += t[x];
  }
  return res;
}

void Cdq1(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1, posr, posl = l;
  Cdq1(l, mid), Cdq1(mid + 1, r);
  sort(a + l, a + mid + 1, cmp1);
  sort(a + mid + 1, a + r + 1, cmp1);
  for (posr = mid + 1; posr <= r; posr++) {
    while (a[posr].y > a[posl].y && posl <= mid)
      add(a[posl].z, 1), posl++;
    ans[a[posr].x] += query(n) - query(a[posr].z);
  }
  Time++;
}

void Cdq2(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1, posr, posl = l;
  Cdq2(l, mid), Cdq2(mid + 1, r);
  sort(b + l, b + mid + 1, cmp2);
  sort(b + mid + 1, b + r + 1, cmp2);
  for (posr = mid + 1; posr <= r; posr++) {
    while (b[posr].y < b[posl].y && posl <= mid)
      add(b[posl].z, 1), posl++;
    ans[b[posr].x] += query(b[posr].z - 1);
  }
  Time++;
}

int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++)
    val[i] = read(), pos[val[i]] = i;
  for (int i = 1; i <= n; i++) {
    a[i].x = 0, a[i].y = i, a[i].z = val[i];
    b[i].x = 0, b[i].y = i, b[i].z = val[i];
  }
  for (int i = 1; i <= m; i++) {
    int now = read();
    a[pos[now]].x = b[pos[now]].x = m - i + 1;
  }
  sort(a + 1, a + 1 + n, cmp);
  sort(b + 1, b + 1 + n, cmp);
  Cdq1(1, n), Cdq2(1, n);
  for (int i = 1; i <= m; i++) ans[i] += ans[i - 1];
  for (int i = m; i >= 1; i--) cout << ans[i] << '\n';
  return 0;
}