題目鏈接

??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

??待補充