逆序数

思路

这题可以用树状数组做个数组 表示元素 i 是否存在，为1表示存在

第i个元素X的逆序对个数就是在i前面的数并且比i大，即 c[x] ~ c[n]位置为1的个数

树状数组函数getsum(i)表示 数组 所以getsum(n) - getsum(x)表示c[x]到c[n]的为1的个数

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 10005;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
inline int lowbit(int x){
    return x & (-x);
}
int c[100005];
int n;
void updata(int i,int j){//将i点的值更新为j
    while(i <= 100003 ){
        c[i] += j;
        i += lowbit(i);
    }
}
int getsum(int i){//求区间1~i的和
    int ans = 0;
    while(i > 0){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
int main(){
     n = read();
    ll ans = 0;
    for(int i = 1 ; i <= n ;++i){
       int tmp = read();
       ans += getsum(100003) - getsum(tmp);
       updata(tmp,1);
    }
    cout<<ans<<endl;
}