洛谷P3157 [CQOI2011] 动态逆序对 题解

题目链接：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 （需要改成多测并开大空间）

---

题外话：

板子都敲不对。