珂朵莉的数列_牛客博客

题目描述

珂朵莉给了你一个序列，有n×(n+1)/2

个子区间，求出她们各自的逆序对个数，然后加起来输出
输入描述:
第一行一个数 n 表示这个序列 a 的长度

之后一行 n 个数，第i个数表示ai

输出描述:
输出一行一个数表示答案
示例1
输入
复制

10
1 10 8 5 6 2 3 9 4 7

输出
复制

示例2
输入
复制

20
6 0 4 5 8 8 0 6 6 1 0 4 6 6 0 0 7 2 0 5

输出
复制

备注:

对于100%的数据，n <= 1000000 ,0 <= 序列中每个数 <= 1000000000

题解：

如果一个逆序对中两个数的坐标分别是l和r，逆序对（l,r）,我们看有多少区间包含了它？
通过组合排列可以得知，一共有l*(n-r+1)个子区间包含，因为子区间肯定要包含[l,r]，那左区间范围是（1，l）,长度是，右区间是（r，n）长度是n-r+1，相乘即是
至于逆序对我们可以用树状数组来做
但是本题最难的点来了：注意题目范围，题目范围贼大，即便开longlong也难逃一挂，（当然你可以用java来做），这里介绍一个小技巧
统计答案时，我们可以用两个数来存，先用第一个数存答案，当答案大小出国1e18时，我们就将超出部分存到第二个数，这里的超出部分是指第1e18位之后的数，也就是这两位数拼起来就是答案
这部分对应的代码：

ll te=1e18
if(ans[0]>=te)ans[1]+=ans[0]/te,ans[0]%=te;
        add(a[i],i);

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

代码：

//求逆序对个数和
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int g=10.0,eps=1e-9;
const int N=1000000+10,maxn=5000000+10,inf=0x3f3f3f3f;
 
ll a[N],b[N],sum[N];
int lowbit(int x)
{
   
	return x&(-x);
 } 
void add(int i,ll x)
{
   
    while(i<N)
    {
   
        sum[i]+=x;
        i+=lowbit(i);
    }
}
ll query(int i)
{
   
    ll ans=0;
    while(i>0)
    {
   
        ans+=sum[i];
        i-=lowbit(i);
    }
    return ans;
}
ll ans[2];
int main()
{
   
    /*ios::sync_with_stdio(false); cin.tie(0);*/
    ll n,cnt=0;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),b[cnt++]=a[i];
    sort(b,b+cnt);
    cnt=unique(b,b+cnt)-b;
    for(ll i=1;i<=n;i++)a[i]=lower_bound(b,b+n,a[i])-b,a[i]++;//离散化处理 
    ll te=1e18;
    for(ll i=1;i<=n;i++)
    {
   
        ans[0]+=(ll)(n-i+1)*(query(n)-query(a[i]));//逆序对数量 
        if(ans[0]>=te)ans[1]+=ans[0]/te,ans[0]%=te;
        add(a[i],i);
    }
    if(ans[1])printf("%lld%018lld\n",ans[1],ans[0]);
    else printf("%lld\n",ans[0]);
    return 0;
}