题解

相比普通逆序对，这个多了“隐藏数”，怎么处理它是关键

#include<iostream>
#include<algorithm>
using namespace std;
const int N=5e5+5;
typedef long long ll;
struct node{
int x,id;
}a[N];
ll c[N],n,m,ans,b[N];
int lowbit(int x){return x & (-x);}
void update(int x,int v){
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
ll sum(int x){
    ll ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
bool cmp(node a,node b){
    if(a.x!=b.x)return a.x<b.x;
    return a.id<b.id;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].x;
        if(a[i].x==-1)a[i].x=m;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)b[a[i].id]=i;
    update(b[1],1);
    for(int i=2;i<=n;i++){
        ans+=sum(n)-sum(b[i]);
        update(b[i],1);
    }
    cout<<ans;
    return 0;
}