洛谷题单指南-线段树的进阶用法-P3157 [CQOI2011] 动态逆序对

原题链接：https://www.luogu.com.cn/problem/P3157

题意解读：长度为n的序列，序列是1~n的排列，一共m个删除操作，每一个删除之前输出逆序对。

解题思路：

要计算静态的逆序对，可以通过树状数组、权值线段树等方式，时间复杂度都是O(nlogn)

要计算动态的逆序对，算上每一次删除，暴力做法需要O(mnlogn)，需要优化

如果能知道删除的元素对逆序对的贡献，问题就好办了

要知道某个元素对逆序对的贡献，也就是要知道该元素前面有多个比小大，后面有多少比它小，显然是一个区间查询元素个数的问题

可以考虑建立n+1棵权值线段树，根节点为root[]，第root[i]棵线段树维护序列a[1]~a[i]

那么要查询a[x]前面有多少个元素比它大，后面有多少个元素比它小，借助于前缀和思路

前面有多少个元素比它大：可以在root[x-1]的线段树中查询

后面有多少个元素比它小：可以在root[n]的线段树查询 - root[x-1]的线段树查询

如果要删除元素，比如删除a[x]，则需要更新root[x]~root[n]所有线段树，这一步是需要优化，容易想到用树状数组套线段树来优化。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct Node
{
    int L, R;
    int cnt;
} tr[N * 800];
int root[N], idx;
int pos[N]; //记录元素的位置
int n, m;
long long ans;

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

void pushup(int u)
{
    tr[u].cnt = tr[tr[u].L].cnt + tr[tr[u].R].cnt;
}

//更新根为u的线段树v值加o
int update(int u, int l, int r, int v, int o)
{
    if(!u) u = ++idx;
    if(l == r)
    {
        tr[u].cnt += o;
        return u;
    }
    int mid = l + r >> 1;
    if(v <= mid) tr[u].L = update(tr[u].L, l, mid, v, o);
    else tr[u].R = update(tr[u].R, mid + 1, r, v, o);
    pushup(u);
    return u;
}

//在根为u的线段树中查询值在lv~rv范围的数量
int query(int u, int l, int r, int lv, int rv)
{
    if(lv > rv) return 0;
    if(l >= lv && r <= rv) return tr[u].cnt;
    else if(l > rv || r < lv) return 0;
    else
    {
        int mid = l + r >> 1;
        return query(tr[u].L, l, mid, lv, rv) + query(tr[u].R, mid + 1, r, lv, rv);
    }
}

//利用树状数组更新root[pos]~root[n]线段树的v值数量，增加o
void add(int pos, int v, int o)
{
    for(int i = pos; i <= n; i += lowbit(i))
    {
        root[i] = update(root[i], 1, n, v, o);
    }
}

//利用树状数组查询root[1]~root[pos]线段树中值在lv~rv范围的数量
int find(int pos, int lv, int rv)
{
    if(lv > rv) return 0;
    int res = 0;
    for(int i = pos; i; i -= lowbit(i))
    {
        res += query(root[i], 1, n, lv, rv);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    int x;
    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        pos[x] = i;
        //x对逆序对的贡献是前面比x大的元素个数
        ans += find(i - 1, x + 1, n);
        add(i, x, 1);
    }
    while(m--)
    {
        cin >> x;
        cout << ans << endl;
        //删除x则减去x对逆序对的贡献，即减去x前面比x大的元素个数以及x后面比x小的元素个数
        ans -= find(pos[x] - 1, x + 1, n) + find(n, 1, x - 1) - find(pos[x], 1, x - 1);
        add(pos[x], x, -1);
    }
    return 0;
}