记录编号	572290	评测结果	AAAAAAAAAA
题目名称	[CQOI2011]动态逆序对	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	1.013 s
提交时间	2022-06-30 12:03:12	内存使用	7.64 MiB

#include <bits/stdc++.h>

using i64 = long long;

const int N = 2e5+10;
int n, m;

struct rec { int v, del, ans; } a[N];

int c[N];

int lowbit(int x) { return x & -x; }

void add(int x, int y) {
    for (; x <= n + 1; x += lowbit(x)) c[x] += y;
}

int ask(int x) {
    int t = 0;
    for (; x; x -= lowbit(x)) t += c[x];
    return t;
}

int rev[N];
i64 res;

void cdqdiv(int l, int r) {
    if (r - l == 1) return;
    int mid = l + r >> 1;
    cdqdiv(l, mid), cdqdiv(mid, r);

    // 删除 a[i] 之前，匹配的元素的数量
    int i = l + 1, j = mid + 1;
    while (i <= mid) {
        while (a[i].v > a[j].v && j <= r) 
            add(a[j ++].del, 1);
        a[i].ans += ask(m + 1) - ask(a[i].del), ++ i;
    }

    // 复原
    i = l + 1, j = mid + 1;
    while (i <= mid) {
        while (a[i].v > a[j].v && j <= r) 
            add(a[j ++].del, -1);
        ++ i;
    }

    // 删除 a[j] 之前，匹配的元素的数量
    i = mid, j = r;
    while (j > mid) { 
        while (a[i].v > a[j].v && i > l)
            add(a[i --].del, 1);
        a[j].ans += ask(m + 1) - ask(a[j].del), -- j;
    }
    // 复原
    i = mid, j = r;
    while (j > mid) { 
        while (a[i].v > a[j].v && i > l)
            add(a[i --].del, - 1);
        -- j;
    }

    std::sort(a + l + 1, a + r + 1, [&](rec a, rec b) {
        return a.v < b.v;
    });
}

int main() {
    freopen("inverse.in", "r", stdin); 
    freopen("inverse.out", "w", stdout);
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i].v;
        rev[a[i].v] = i;
    }
    for (int i = 1; i <= m; ++ i) {
        int del;
        std::cin >> del;
        a[rev[del]].del = i;
    }
    for (int i = 1; i <= n; ++ i) 
        if (a[i].del == 0) a[i].del = m + 1;

    // 求初始逆序对
    for (int i = 1; i <= n; ++ i) {
        res += ask(n + 1) - ask(a[i].v);
        add(a[i].v, 1);
    }   
    for (int i = 1; i <= n; ++ i) 
        add(a[i].v, -1);

    // cdqdiv
    cdqdiv(0, n);
    std::sort(a + 1, a + n + 1, [&](rec a, rec b) {
        return a.del < b.del;
    });
    for (int i = 1; i <= m; ++ i) 
        std::cout << res << '\n', res -= a[i].ans;
    return 0;
}