牛客练习赛7E珂朵莉的数列

题意：求所有子区间的逆序数对数之和

题解:树状数组维护，对于每一对逆序数(l,r)属于l*(n-r+1)个区间，计算每一对对结果的贡献即可，可用树状数组维护，sum维护(n-r+1)，按逆序数那样操作

这题最狗的地方是爆longlong，java又超时。。。，用了一个小技巧，避免爆longlong

#include<bits/stdc++.h>

#define fi first

#define se second

#define ll long long

#define ull unsigned long long

#define mp make_pair

#define pb push_back

#define mod 1000000007

#define pii pair<int,int>

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const int g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f;

ll a[N],b[N],sum[N];

void add(int i,ll x)

{

    while(i<N)

    {

        sum[i]+=x;

        i+=i&(-i);

    }

}

ll query(int i)

{

    ll ans=;

    while(i>)

    {

        ans+=sum[i];

        i-=i&(-i);

    }

    return ans;

}

int main()

{

    /*ios::sync_with_stdio(false);

    cin.tie(0);*/

    ll n,cnt=;

    scanf("%lld",&n);

    for(ll i=;i<=n;i++)scanf("%lld",&a[i]),b[cnt++]=a[i];

    sort(b,b+cnt);

    cnt=unique(b,b+cnt)-b;

    for(ll i=;i<=n;i++)a[i]=lower_bound(b,b+n,a[i])-b,a[i]++;

    ll ans[]={},te=1e18;

    for(ll i=;i<=n;i++)

    {

        ans[]+=(ll)(n-i+)*(query(n)-query(a[i]));

        if(ans[]>=te)ans[]+=ans[]/te,ans[]%=te;

        add(a[i],i);

    }

    if(ans[])printf("%lld%018lld\n",ans[],ans[]);

    else printf("%lld\n",ans[]);

    return ;

}

/*******************

3

0 0 0

*******************/