洛谷P3157 [CQOI2011] 动态逆序对 题解
题意：
对于序列 \(a\)，它的逆序对数定义为集合
\[ \{(i,j)\mid i < j \,\land\, a_i > a_j\} \] 的元素个数。现在给出 \(1\sim n\) 的一个排列，按照某种顺序依次删除 \(m\) 个元素。
你的任务是在每次删除一个元素之前统计整个序列的逆序对数。
输入格式：
第一行包含两个整数 \(n\) 和 \(m\)，即初始元素的个数和删除的元素个数。
以下 \(n\) 行，每行包含一个 \(1 \sim n\) 之间的正整数，即初始排列。
接下来 \(m\) 行，每行一个正整数，依次为每次删除的元素。
输出格式：
输出包含 \(m\) 行，依次为删除每个元素之前，逆序对的个数。
数据范围：
\(1\le n \le 10^5,~1\le m \le 50000\)。
考虑 CDQ 分治。
方便起见，我们把初始的数看作 \(n\) 个添加操作，修改为 \(f_i=1\) （删除则为 \(-1\) ）。
记 \(t_i\) 为时间戳（非修改则为 \(0\) ），\(x_i\) 为元素编号，\(y_i\) 为元素的值。
那么，一次修改 \((t_i,x_i,y_i,f_i)\) 对答案的增量 \(\Delta\) 为以下条目之和：
- 满足 \(t_j < t_i,~x_j >x_i,~y_j < y_i\) 的 \(j\) 的数量乘以 \(f_i\) 。（自己做大哥的情况）
- 满足 \(t_{j} < t_{i},~x_j < x_i,~y_j > y_i\) 的 \(j\) 的数量乘以 \(f_i\) 。（自己做小弟的情况）
比如序列 \(a=\{2,1\}\) ，删除 \(2\) 的操作 \((1,1,2,-1)\) 对答案的增量为 \[ 1\times (-1) + 0\times(-1) = -1 \] 注意这个是增量，别忘了前缀和一下。
时间复杂度 \(\mathcal{O}(n \log^2 n)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 55))
int n, tot, id[N], ans[N], tr[N];
struct node { int t, x, y, f; } a[N];
bool cmp(node x, node y) { return x.x == y.x ? x.t < y.y : x.x < y.x; }
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += v; }
int qry(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[i]; return r; }
void cdq(int l, int r)
{
if(l == r) return;
int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r);
sort(a + l, a + 1 + mid, cmp); sort(a + 1 + mid, a + 1 + r, cmp);
int j = l;
for(int i = mid + 1; i <= r; i++)
{
for(; a[j].x <= a[i].x && j <= mid; j++) add(a[j].y, a[j].f);
ans[a[i].t] += a[i].f * (qry(n) - qry(a[i].y));
}
for(int i = l; i < j; i++) add(a[i].y, -a[i].f);
j = mid;
for(int i = r; i > mid; i--)
{
for(; a[j].x >= a[i].x && j >= l; j--) add(a[j].y, a[j].f);
ans[a[i].t] += a[i].f * qry(a[i].y - 1);
}
for(int i = mid; i > j; i--) add(a[i].y, -a[i].f);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int q; cin >> n >> q;
for(int i = 1, x; i <= n; i++) { cin >> x; a[++tot] = {0, i, x, 1}; id[x] = i; }
for(int i = 1, x; i <= q; i++) { cin >> x; a[++tot] = {i, id[x], x, -1}; }
cdq(1, tot);
for(int i = 1; i <= q; i++) ans[i] += ans[i - 1];
for(int i = 0; i < q; i++) cout << ans[i] << '\n';
return 0;
}双倍经验：UVA11990 ``Dynamic'' Inversion （需要改成多测并开大空间）
题外话：
板子都敲不对。
