题目描述:
给出一个序列,求序列中所有子区间中逆序对个数的和。
做法:
将每一个逆序对分开来看,假设存在···a【l】···a【r】···,且a【l】>a【r】,那么包含这个逆序对的区间就是左端点在1-l,右端点在r-n的任意一个区间,那么这样的区间一共是l*(n-r+1)个,考虑用树状数组解决,但是题目的数据较大,另外需要离散化,离散后对于a【i】,可以在树状数组中维护其左边界数量,右边界的数量则是(n-i+1)每次相乘累加即可,答案爆long long可以用__int128。

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define  endl '\n'
#define all(s) s.begin(),s.end()
#define lowbit(x) (x&-x)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mem(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define pb push_back
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int mod=1e9+7;
const double eps=1e-8;
const int inf=0x3f3f3f3f;
const int N=1e6+10;
ll a[N],bit[N];
vector<int>v;
void add(int x,int k)
{
    while(x<N){
        bit[x]+=k;
        x+=lowbit(x);
    }
}
ll sum(int x)
{
    ll ans=0;
    while(x>0){
        ans+=bit[x];
        x-=lowbit(x);
    }
    return ans;
}
int getid(int x)
{
    return lower_bound(all(v),x)-v.begin()+1;
}
void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
int main()
{
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],v.pb(a[i]); 
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    __int128 ans=0;
    for(ll i=1;i<=n;i++){
        int now=getid(a[i]);
        ans+=ll(sum(N-1)-sum(now))*(n-i+1);
        add(now,i);
    }
    print(ans);
}