逆序对

2017-10-26

在一个序列中，如果存在a[i]j，则称a[i]，a[j]为逆序对。

如1 5 7 2 4中，逆序对有{5，2}，{5，4}，{7，2}，{7，4}。
方法1 归并

#include <cstdio>
using namespace std;
int a[1000010],b[1000010];
long long ans=0;
int n;
void merge(int l,int r) {
    if(l==r)return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int s1=l,s2=mid+1,p=l-1;
    while(s1<=mid&&s2<=r){
        if(a[s1]<=a[s2]){
            b[++p]=a[s1];
            s1++;
        }
        else {
            b[++p]=a[s2];
            s2++;
            ans+=mid-s1+1;//求个数
        }
    }
    while(s1<=mid){
        b[++p]=a[s1];
        s1++;
    }
    while(s2<=r){
        b[++p]=a[s2];
        s2++;
    }
    for(register int i=l;i<=r;i++){
        a[i]=b[i];
    }//更新
}
int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;i++)scanf("%d",&a[i]);
    merge(1,n);
    printf("%lld",ans);
    return 0;
}

方法2树状数组
暂时不会。

例题
有n项寒假作业。a给每项寒假作业都定义了一个疲劳值Ai，表示抄这个作业所要花的精力。b现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于k？

简单地说，给定n个正整数A1,A2,A3,…,An，求出有多少个连续的子序列的平均值不小于k。

我们可以求前缀和sum，若要满足题意则(sum[j]-sum[i-1])/(j-i+1)>=k。
化简得(a[i]-k)+(a[i+1]-k)+…+(a[j]-k)>=0；
我们可以另设一个数组 b[]，使 b[i]=a[i]-k；
所以b[i]+b[i+1]+…+b[j]>=0
所以可以在用前缀和
pre[j]-pre[j-1]>=0
所以，这是一个不逆序对（乱定义）。

#include <cstdio>
using namespace std;
int a[1000010],b[1000010],pre[1000010],k;
long long ans=0;
int n;
void merge(int l,int r) {
    if(l==r)return;
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1,p=l-1;
    while(i<=mid&&j<=r){
        if(pre[i]<=pre[j]){
            b[++p]=pre[i];
            i++;
            ans+=r-j+1;
        }
        else {
            b[++p]=pre[j];
            j++;
        }
    }
    while(i<=mid){
        b[++p]=pre[i];
        i++;
    }
    while(j<=r){
        b[++p]=pre[j];
        j++;
    }
    for(register int i=l;i<=r;i++){
        pre[i]=b[i];
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(register int i=1;i<=n;i++)scanf("%d",&a[i]),pre[i]=pre[i-1]+a[i]-k;
    merge(0,n);//记得从0开始。
    printf("%lld",ans);
    return 0;
}