题目地址：洛谷：【P3157】[CQOI2011]动态逆序对 – 洛谷、BZOJ：Problem 3295. — [Cqoi2011]动态逆序对

题目描述

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

输入输出格式

输入格式：
输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

输出格式：
输出包含m行，依次为删除每个元素之前，逆序对的个数。

输入输出样例

输入样例#1：

5 4
1
5
3
4
2
5
1
4
2

输出样例#1：

5
2
2
1

说明

N<=100000 M<=50000

题解

树套树（BIT套动态开点权值线段树）

考虑倒着插回去，插一个计算一次答案。关键在于，如果我们直接用主席树写这个，插回去的复杂度是O(n \log n)的，因为要对插入位置及以后的每个点更新信息。我们套一个BIT上去，令BIT的每个节点的权值线段树维护该节点覆盖范围内的数值分布情况。这样，每次插入在BIT上影响到的点是O(\log n)级别的，也就是说，总复杂度降为了O(\log^2 n)。
由于我们不可能真的每个点开一棵线段树，空间O(n^2)不可接受，就需要用到动态开点和垃圾回收的手段来优化空间使用。优化后的空间是O(n \log^2 n)的。

CDQ分治

还没学。

代码

树套树

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int n, m;

struct Node {
    int lch, rch, cnt;
} tr[MAXN * 90];
int rt[MAXN], tot;

int sta[MAXN * 90], stop;

inline void delnode(int p) {
    if(!p) return;
    sta[stop++] = p;
}

inline int newnode() {
    if(!stop) return ++tot;
    int p = sta[--stop];
    memset(tr + p, 0, sizeof(Node));
    return p;
}

inline void insert(int &o, int l, int r, int x) {
    int p = newnode(); tr[p] = tr[o]; delnode(o); o = p;
    tr[p].cnt++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x);
    else insert(tr[o].rch, mid + 1, r, x);
}

inline int querylar(int o, int l, int r, int x) {
    if(l == r) return 0;
    int mid = (l + r) >> 1;
    if(x <= mid) return tr[tr[o].rch].cnt + querylar(tr[o].lch, l, mid, x);
    else return querylar(tr[o].rch, mid + 1, r, x);
}

inline int querysma(int o, int l, int r, int x) {
    if(l == r) return 0;
    int mid = (l + r) >> 1;
    if(x <= mid) return querysma(tr[o].lch, l, mid, x);
    else return tr[tr[o].lch].cnt + querysma(tr[o].rch, mid + 1, r, x);
}

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

inline void add(int x, int v) {
    for(int i = x; i <= n; i += lowbit(i)) {
        insert(rt[i], 1, n, v);
    }
}

inline int query(int x, int v) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += querylar(rt[i], 1, n, v);
    for(int i = n; i; i -= lowbit(i)) res += querysma(rt[i], 1, n, v);
    for(int i = x; i; i -= lowbit(i)) res -= querysma(rt[i], 1, n, v);
    return res;
}

int a[MAXN], del[MAXN], idx[MAXN];
LL anss[MAXN];
bool isdel[MAXN];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        idx[a[i]] = i;
    }
    for(int i = m; i; i--) {
        del[i] = readint();
        isdel[del[i]] = true;
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!isdel[a[i]]) {
            add(i, a[i]);
            ans += query(i, a[i]);
        }
    }
    for(int i = 1; i <= m; i++) {
        add(idx[del[i]], del[i]);
        ans += query(idx[del[i]], del[i]);
        anss[m - i + 1] = ans;
    }
    for(int i = 1; i <= m; i++) {
        printf("%lld\n", anss[i]);
    }
    return 0;
}

CDQ分治