题目描述

珂朵莉给了你一个序列，有个子区间，求出她们各自的逆序对个数，然后加起来输出

输入描述:

第一行一个数 n 表示这个序列 a 的长度之后一行 n 个数，第i个数表示ai

输出描述:

输出一行一个数表示答案

题解

直接搞肯定不行了，那我们就考虑每一对逆序数对于答案的贡献吧。
假如a[i]和a[j]组成一对逆序对，那么这对逆序对对于所有区间左界在[1,i]的范围，区间右界在[j,n]的范围的区间都有贡献，即它对答案贡献是。那我们就好搞了，用权值树状数组维护每个数字对应的坐标和，然后枚举j，在区间里面找大于的数字的坐标和，然后算出他的贡献加到答案里就好啦。
最后注意答案爆long long，开了long long也见祖宗呜呜呜，直接用__int128加手写一个输出函数就OK了。

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=1e6+100;
ll a[N],tree[N];
int n;
vector<int> v;
int lowbit(int x){
    return -x&x;
}
void add(int x,int k){
    while(x<=n){
        tree[x]+=k;
        x+=lowbit(x);
    }
}
ll query(int x){
    ll sum=0;
    while(x>0){
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
int where(int x){
    return lower_bound(all(v),x)-v.begin()+1;
}
////////////////////////////////////////////////////////////////////////
int main(){
    n=gn();
    repi(i,1,n)a[i]=gn(),v.pb(a[i]);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    __int128_t ans=0;
    repi(i,1,n){
        ans+=(query(v.size()+1)-query(where(a[i])))*(n-i+1);
        add(where(a[i]),i);
    }
    print(ans),putchar(10);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/