逆序数《求所有子序列的逆序对个数的和

题目

玲珑杯1180

题解

一对逆序对对答案的贡献是2^(n-2)
故统计出逆序对个数后乘上即可
注意序列长1的情况什么什么的
O( nlogn )

代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long int
#define mod 1000000007
LL a[1000005],b[1000005];
LL n;
LL ans;//极限情况500000*500000会爆，所以开LL
void mersort(LL x,LL y)
{
    if(y-x<=1)
        return ;
    LL mid=(x+y)/2;
    mersort(x,mid);
    mersort(mid,y);
    LL p=x,i=x,q=mid;
    while(p<mid||q<y)
    {
        if(q==y||(p<mid&&a[p]<=a[q]))//注意，不是a[p]<=a[mid],弄清比较的对象
            //x到y排序，所以应该和a[q]比，从而把后面的一到前面去。
            b[i++]=a[p++];
        else if(p==mid||a[p]>a[q])
        {
            if(p<mid) ans+=(mid-p);
            b[i++]=a[q++];
        }
    }
    for(LL i=x; i<y; i++)
        a[i]=b[i];
}
LL qu(LL a,LL b)
{
    LL anss=1;
    while(b)
    {
        if(b&1)
        {
            anss=(anss*a)%mod;
        }
        b/=2;
        a=(a*a)%mod;
    }
    return anss;
}
int main()
{
    while(~scanf("%lld",&n))
    {
        //if(n==1) continue;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(LL i=0; i<n; i++)
            scanf("%lld",&a[i]);
        ans=0;
        mersort(0,n);
        LL anss=qu(2,n-2);
        ans%=mod;
        printf("%lld\n",(ans*anss)%mod);
    }
    return 0;
}