题面

luogu

题解

树套树（树状数组套动态开点线段树）

静态使用树状数组求逆序对就不多说了

用线段树代替树状数组，外面套树状数组统计每个点逆序对数量

设
\(t1[i]\)为\(i\)前面有多少个数比\(a[i]\)大
\(t2[i]\)为\(i\)后面有多少个数比\(a[i]\)小
那么当删除\(a[i]\)时
\(ans\) \(=\) \(ans-(t1[i]+t2[i])+\)\(i\)前面有多少个数比\(a[i]\)大且已经被删了+\(i\)后面有多少个数比\(a[i]\)小且已经被删了

用树套树维护就好了

Code

#include<bits/stdc++.h>

#define LL long long
#define RG register

using namespace std;

inline int gi() {
    RG int x = 0; RG char c = getchar(); bool f = 0;
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') c = getchar(), f = 1;
    while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
    return f ? -x : x;
}
const int N = 100010, M = 50010;
int t[N], n, m;
LL ans;
#define lowbit(x) (x&(-x));
inline int Tsum(int x) {
    int s = 0;
    while (x) s += t[x], x -= lowbit(x);
    return s;
}
inline void Tadd(int x) {while (x <= n) t[x]++, x += lowbit(x);}

struct node {
    int ls, rs, v;
}st[6000010];
int root[N];

int a[N], t1[N], t2[N], id[N], cnt;

void update(int &rt, int l, int r, int k) {
    if (!rt) rt = ++cnt;
    st[rt].v++;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (k <= mid) update(st[rt].ls, l, mid, k);
    else update(st[rt].rs, mid+1, r, k);
}

int sum(int rt, int l, int r, int L, int R) {
    if (!rt) return 0;
    if (L <= l && r <= R) return st[rt].v;
    int mid = (l + r) >> 1, s = 0;
    if (L <= mid) s = sum(st[rt].ls, l, mid, L, R);
    if (R > mid) s += sum(st[rt].rs, mid+1, r, L, R);
    return s;
}

int query(int x, int l, int r) {
    int s = 0;
    if (l > r) return 0;
    while (x) {
        s += sum(root[x], 1, n, l, r);
        x -= lowbit(x);
    }
    return s;
}


void insert(int x, int k) {
    while (x <= n) {
        update(root[x], 1, n, k);
        x += lowbit(x);
    }
    return ;
}

int main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi(), m = gi();
    for (int i = 1; i <= n; i++) a[i] = gi(), id[a[i]] = i;
    for (int i = 1; i <= n; i++) {
        t1[i] = Tsum(n)-Tsum(a[i]);
        ans += t1[i];
        Tadd(a[i]);
    }
    memset(t, 0, sizeof(t));
    for (int i = n; i; i--) {
        t2[i] = Tsum(a[i]-1);
        Tadd(a[i]);
    }
    while (m--) {
        int x = gi(), w = id[x];
        printf("%lld\n", ans);
        ans -= (t1[w]+t2[w]);
        ans += query(w-1, x+1, n);
        ans += query(n, 1, x-1)-query(w, 1, x-1);
        insert(w, x);
    }
    return 0;
}

洛谷 P3157 [CQOI2011]动态逆序对

原文：https://www.cnblogs.com/zzy2005/p/10198825.html