珂朵莉的数列

题目链接
参考博客

这里先给出 __int128和利用vector的unqiue 配合erase 去重
__int128 , vector的unqiue 配合erase 去重

刚开始看这个题，就是简单的求逆序对 所产生的贡献，对于一个逆序对 [i , j]他们所产生的贡献是 l * (n - j)个，所以我们可以枚举j如果 j 前面有m个数大于它，那这m个数字与j所产生的贡献即为这m个数字的下标和 乘以 (n - j + 1),所以我们在用树状数组求逆序对的时候，要去维护它们的下标和
但是由于这个题的数据范围是1e9但是数字的数量只有1e6所以要进行离散化，而且答案的数据太大了
long long 也会爆，所以这时候要用__int128

代码

#include <bits/stdc++.h>

using namespace std;

typedef __int128  LL;

const int maxn = 1000000 + 5;
const int Mod = 1e9 + 7;

int n,m;
LL c[maxn];
vector <int> a,b;

int GCD(int a,int b)
{
    int temp;
    while(b){
        temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

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

void insert(LL x,LL y)
{
    for(int i = x; i <= a.size(); i += lowbit(i)){
        c[i] += y;
    }
}

LL Query(LL x)
{
    LL res = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        res += c[i];
    }
    return res ;
}

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

int main()
{
    //std::ios::sync_with_stdio(false);
    memset(c,0,sizeof c);
    scanf("%d",&n);
    for(int i  = 1; i <= n;  i++){
        int x;
        scanf("%d",&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(a.size()) - Query(pos)) * (n - i);
        insert(pos,1 + i);
        //我们可以发现当前数字与它前面数字组成的逆序对的贡献是
        //它前面比他大的数字的下标和 * 乘以自己后面的下标个数。
        //所以要用树状数组去维护下标和
    } 
    output(res);
    return 0;
}