题目链接

  UVA11990 ``Dynamic’’ Inversion

题意

  给一个 1~n 的排列A，要求按照某种顺序删除一些数（其他数顺序不变），输出每次删除之前逆序对的数目。所谓逆序对数，就是满足i<j 且A[i]>A[j]的有序对(i,j)的数目。

输入格式

  输入包含多组数据，每组数据的第一行为两个整数n 和m（1≤n≤200 000，1≤m≤100 000）；接下来的n 行表示初始排列；接下来的m 行按顺序给出删除的整数，每个整数保证不会删除两次。输入结束标志为文件结束符（EOF）。输入文件大小不超过5MB。

输出格式

  对于每次删除，输出删除之前的逆序对数。

分析

  核心思想是先求出初始逆序对个数，然后减去每次删除元素后受影响的逆序对个数。初始逆序对个数利用树状数组可以求出。作为嵌套和分块数据结构的经典题目，下面从CDQ分治、嵌套（本题是树状数组套BST）、分块、k-D Tree这四种常见解法分别做分析。

CDQ分治

  考虑给每个元素三个属性 $t,p,v$，分别表示这个元素的删除时间 $t$，位置 $p$，值 $v$，那删除元素 $i$ 受影响的逆序对 $(i,j)$ 需要满足以下条件 $(t_i<t_j\wedge p_i<p_j\wedge v_i>v_j)\vee (t_i<t_j\wedge p_i>p_j\wedge v_i<v_j)$，套用CDQ分治处理三维偏序问题的思想即可解决：排序处理第一维 $t_i$，分治处理第二维 $p_i$，树状数组处理第三维 $v_i$。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;#define N 200100
struct {int t, p, v;} e[N]; int a[N], p[N], c[N], f[N], m, n; long long s;bool cmp(int i, int j) {return e[i].t < e[j].t;
}void solve(int s, int t) {if (t - s == 1) return;int m = (s+t) / 2, h = m, q = t-1;solve(s, m); solve(m, t);for (int i=s; i<m; ++i) {while (h < t && e[a[h]].p < e[a[i]].p) for (int x=e[a[h++]].v; x; x -= x&-x) ++c[x];if (e[a[i]].t < ::m) for (int x=e[a[i]].v+1, j=e[a[i]].t; x<=n; x += x&-x) f[j] += c[x];}for (int i=m; i<h; ++i) for (int x=e[a[i]].v; x; x -= x&-x) --c[x];for (int i=m-1; i>=s; --i) {while (q >=m && e[a[q]].p > e[a[i]].p) for (int x=e[a[q--]].v; x<=n; x += x&-x) ++c[x];if (e[a[i]].t < ::m) for (int x=e[a[i]].v-1, j=e[a[i]].t; x; x -= x&-x) f[j] += c[x];}if (s == 0 && t == n) return;for (int i=t-1; i>q; --i) for (int x=e[a[i]].v; x<=n; x += x&-x) --c[x];for (int i=s; i<t; ++i) p[i] = a[i];for (int i=s, j=m, k=s; k<t; ++k) a[k] = i == m || (j < t && e[p[j]].p < e[p[i]].p) ? p[j++] : p[i++];
}void solve() {memset(c, s = 0, sizeof(c));for (int i=0; i<n; ++i) {cin >> e[i].v; e[i].p = p[e[i].v] = i; e[i].t = m; a[i] = i;for (int x = e[i].v+1; x<=n; x += x&-x) s += c[x];for (int x = e[i].v; x; x -= x&-x) ++c[x];}for (int i=0, v; i<m; ++i) cin >> v, f[e[p[v]].t = i] = 0;sort(a, a+n, cmp); memset(c, 0, sizeof(c)); solve(0, n);for (int i=0; i<m; s -= f[i++]) cout << s << endl;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> m) solve();return 0;
}

嵌套（树状数组套BST）

  嵌套的解题思路引用自《训练指南》410页：

  令 $larger(p,v)$ 表示 $A_p>v$ 是否成立（1 表示成立，0 表示不成立），则“前 k 个数有多少个比 v 大”等于 larger(1,v)+larger(2,v)+larger(3,v)+…+larger(k,v)。
  注意，这是一个前缀查询，因此可以用 Fenwick 树维护。回忆第 3 章中对 Fenwick 树的 C 数组的定义$$C_i=A_{i-lowbit(i)+1}+A_{i-lowbit(i)+2}+\dots +A_i$$  对应到本题中，$C_i$ 的值实际上等于 “$A_{(}i-lowbit(i)+1),\dots ,A_i$ 中有多少个元素比 v 大”。考虑到本题还有删除操作，可以用第3 章介绍过的名次树来实现这些 $C_i$。这样，我们得到了一个 “Fenwick 树套名次树”的特殊数据结构，在$O(lo{g}^{2}n)$时间内解决了本题。
  具体来说，对于每个 $i$，我们用 $A_{i-lowbit(i)+1},\dots ,A_i$ 这些数构造第 $i$ 棵名次树，支持两个操作：删除元素和统计树里有多少个元素小于某个 $k$。当删除第 $i$ 个位置的数v 时，按照 Fenwick 树算法计算 $Q(i-1)+\dots +Q(i-lowbit(i-1))\dots$这里的 $Q(i)$ 就是查找第 $i$ 棵BST 中大于 $v$ 的个数。
  这里的名次树并不需要用 Treap 或者伸展树实现，因为它只有删除没有插入和修改。如果给每个结点添加一个“是否已删除”的标记，就可以在不改变树结构的情况下支持删除操作。换句话说，只要在预处理时把每棵名次树都建成完全平衡的二叉树，则两个操作的时间复杂度总是对数级别的。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;#define N 200100
int a[N], p[N], c[N], e[N], m, n, t; long long s;
struct node {int v, d; node *l, *r;} q[N*18], *h[N];node* build(int a, int b) {if (a >= b) return NULL;node *r = q + t++; int m = (a+b)>>1; *r = {e[m], 0, build(a, m), build(m+1, b)};return r;
}int query(const node *p, int s, int v) {if (!p) return 0;if (p->v >= v) return query(p->l, s>>1, v);int ld = (p->l ? p->l->d : 0), c = p->d - ld - (p->r ? p->r->d : 0);return (s>>1) - ld + 1-c + query(p->r, s-1 - (s>>1), v);
}int query(int x) {int a = x-1, b = 0, e = 0;for (int i=x; i; i -= i&-i) a -= c[i];for (int i=p[x]-1; i; i -= i&-i) b += (i&-i) - h[i]->d, e += query(h[i], i&-i, x);return b-e + a-e;
}void remove(node *p, int v) {p->d ++;if (p->l && p->v > v) remove(p->l, v);if (p->r && v > p->v) remove(p->r, v);
}void solve() {memset(c, s = t = 0, sizeof(c));for (int i=1; i<=n; ++i) {cin >> a[i]; p[a[i]] = i;for (int x = a[i]+1; x<=n; x += x&-x) s += c[x];for (int x = a[i]; x; x -= x&-x) ++c[x];int cc = i&-i;for (int j=i-cc+1, k=0; j<=i; ++j) e[k++] = a[j];sort(e, e+cc);h[i] = q + t++; *h[i] = {e[cc>>1], 0, build(0, cc>>1), build((cc>>1)+1, cc)};}memset(c, 0, sizeof(c));while (m--) {int x; cin >> x;cout << s << endl;s -= query(x);for (int i=x; i<=n; i += i&-i) ++c[i];for (int i=p[x]; i<=n; i += i&-i) remove(h[i], x);}
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> m) solve();return 0;
}

分块

  设将原序列分成长度为 $s$ 的块，对于每个块维护一个有序数组。每次删除一个数，容易想到在它前面比它大的数和在它后面比它小的数的计数会被清除，所以对于每个块二分查找个数并相加，对删除的数所在的块暴力统计即可。删除时，直接在原数组中将其标记，有序数组中找到它并将其移至所在块最后方。
  单次查询的时间复杂度为 $O(\frac{n}{s}\log s+s)$，单次删除的时间复杂度为 $O(s+\log s)$，因此单次查询及删除总的时间复杂度为$O(\frac{n}{s}\log s+s)$。
  本题限时3秒，分块的大小s将成为卡常限制。如果取 $s=\sqrt{n}$ 则总的查询和删除的时间复杂度为$O(m\sqrt{n}\log \sqrt{n})$，提交容易超时；取 $s=\frac{n}{\sqrt{m}}$ 整体来说时间复杂度$O(m\sqrt{m}\log \frac{n}{\sqrt{m}}+n\sqrt{m})$更优（因为1≤n≤200 000，1≤m≤100 000，m≤n）。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;#define N 200100
#define M 634
int b[M][M], a[N], p[N], c[N], t[M], m, n, y, z; long long s; bool f[N];inline int query(int v) {int s = 0, h = p[v] / z; f[p[v]] = true;for (int i=0; i<h; ++i) s += t[i] - (upper_bound(b[i], b[i]+t[i], v) - b[i]);for (int i=h+1; i<y; ++i) s += lower_bound(b[i], b[i]+t[i], v) - b[i];for (int i=z*h; i<p[v]; ++i) if (a[i] > v && !f[i]) ++s;for (int i=p[v]+1, j=min(z*h+z, n); i<j; ++i) if (a[i] < v && !f[i]) ++s;for (int i=lower_bound(b[h], b[h]+t[h], v) - b[h], j=--t[h]; i<j; ++i) b[h][i] = b[h][i+1];return s;
}void solve() {memset(c, s = 0, sizeof(c)); z = n/sqrt(m)+1; y = (n + z-1) / z;for (int i=0; i<n; ++i) {cin >> a[i]; f[p[a[i]] = i] = false; b[i/z][i%z] = a[i];for (int x = a[i]+1; x<=n; x += x&-x) s += c[x];for (int x = a[i]; x; x -= x&-x) ++c[x];}for (int i=0; i<y; ++i) t[i] = i+1 < y ? z : n - (y-1)*z, sort(b[i], b[i] + t[i]);while (m--) {cout << s << endl;int v; cin >> v;if (m == 0) return;s -= query(v);}
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> m) solve();return 0;
}

k-D Tree

  待补充