题解 | #Inverse Pair#

I 题题解

思路

题意:通过对 a 中若干个元素 加1(每个元素只能加1次)，使得逆序对的数目变少，问逆序对数目 最少可变为几
因为 a 是 1 到 n 的全排列，即 [1,n] 中每个元素均出现且只出现一次
所以 我们每次 加1操作 最多消掉一个逆序对 ，该逆序对 满足 i < j && ai > aj && ai = aj+1
我们把这样的逆序对 称为 "目标逆序对”
所以，我们只需要统计有多少个 目标逆序对就行，刚开始时的逆序对数目 减去 目标逆序对的数目 就是答案

ps: 需注意一种特殊情况:
假设存在 逆序对 : i < j && ai > aj && ai = aj+1
同时也存在 逆序对: j < k && aj > ak && aj = ak + 1
比如 4、3、2
我们对 3 进行加一 操作后，变成了 4、4、2
此时 第二个位置上的数 和 第三个位置上的数 不再构成目标逆序对

Code

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

const int N = 3e5+10;

struct node{
    int val,pos;
    bool operator < (const node & x) const { return val < x.val ; }
}p[N];
int tr[N];
int n;
ll num;

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

void add(int x){
    for(int i=x;i<=N;i+=lowbit(i)) tr[i]++;
}

int query(int x){
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
    return ans;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x;  cin>>x;
        p[i]={x,i};
        add(x);
        num+=i-query(x); // 树状数组求逆序对
    }
    sort(p+1,p+1+n);

    for(int i=1;i<n;i++)  if(p[i].pos>p[i+1].pos) num--,i++; // 避免出现上述的特殊情况，从而多减
    cout<<num<<endl;

    return 0;
}