维护区间[1,i-1]本质不同逆序对的个数板子（不同种类的逆序对个数）

点击查看代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 9;
int T, n, cnt, flag, maxn;
LL ans;
int a[N],c[N],vis[N];
int lowbit(int x){return x&(-x);
}
void Add(int x){while(x<=n){c[x]++;x+=lowbit(x);}
}
int Sum(int x){int tot=0;while(x){tot+=c[x];x-=lowbit(x);}return tot;
}
void solve()
{cin>>n;memset(c,0,sizeof(int)*(n+9));memset(vis,0,sizeof(int)*(n+9));maxn=cnt=flag=0; ans=0;for(int i=1;i<=n;i++)cin>>a[i];vis[a[1]]=1; Add(a[1]);for(int i=2;i<=n;i++){if(!vis[a[i]]) vis[a[i]]=1,Add(a[i]);ans+=Sum(a[1])-Sum(a[i]);}cout<<"\n";
}
int main(){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);solve();return 0;
}