【每日一题】珂朵莉的数列

description：
所有子区间中逆序对的个数

solution：
暴力肯定是不可取的 考虑一个逆序对的贡献，当且仅当一个区间包含了该逆序对才对该区间有贡献，根据这点，假设左边界为i，右边界为j，则贡献为i * (n - j + 1)。
根据这个思路，我们枚举右边界j，来计算有多少符合的左边界i来计算贡献，求他们的下标和，下标和用树状数组维护即可。

code:

#include <bits/stdc++.h>

using namespace std;

#define LL __int128

const int N = 1e6 + 5;

LL c[N];

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

void update(LL i,LL x){
    for(;i < N;i += lowbit(i)){
        c[i] += x;
    }
}

LL query(LL i){
    LL sum = 0;

    for(;i > 0;i -= lowbit(i)){
        sum += c[i];
    }

    return sum;
}

void out(LL x){
    if(x < 10){
        putchar(x + '0');
        return ;
    }
    out(x / 10);
    putchar(x % 10 + '0');
}

vector <int> a,b;

int main(){
    ios::sync_with_stdio(0);
    int n;
    cin >> n;

    for(int i = 0;i < n;i ++){
        int x;
        cin >> x;
        a.push_back(x);
        b.push_back(x);
    }

    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());

    LL res = 0;
    for(int i = 0;i < n;i ++){
        int pos = lower_bound(a.begin(),a.end(),b[i]) -a.begin() + 1;
        res += 1LL*(query(n) - query(pos)) *(n - i);
        update(pos,i + 1);
    }

    out(res);

    return 0;
}