归并排序求逆序数

短命女 2022-08-05 08:56 162阅读 0赞

感觉还是数组用全局的比较快一些

练习题目：[http://acm.hdu.edu.cn/showproblem.php?pid=4911][http_acm.hdu.edu.cn_showproblem.php_pid_4911]

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=1000010;
    int a[N];
    int b[N>>1];
    int c[N>>1];
    
    ll Merge(int l,int mid,int r)
    {
        ll cnt=0;
        int n1=mid-l+1;
        int n2=r-mid;
        memcpy(b,a+l,sizeof(int)*n1);
        memcpy(c,a+mid+1,sizeof(int)*n2);
        b[n1]=c[n2]=inf;
        int ai=l,bi=0,ci=0;
        while(ai<=r)                 //此时b c数组都是有序的了
        {
            if(c[ci] >= b[bi]) a[ai++]=b[bi++];
            else
            {
                a[ai++]=c[ci++];
                cnt += n1-bi;       //bi后面的元素都比那个元素要大，因为是有序的
            }
        }
    
        return cnt;
    
    }
    
    ll merge_sort(int l,int r)
    {
        if(l<r)
        {
            ll cnt=0;
            int mid=(l+r)>>1;
            cnt += merge_sort(l,mid);     //单独在左边的
            cnt += merge_sort(mid+1,r);   //单独在右边的
            cnt += Merge(l,mid,r);        //分布在两边的
            return cnt;
        }
        return 0;
    }
    
    
    int main()
    {
        int T=in();
        while(T--)
        {
            int n;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                a[i]=in();
            }
            ll cnt=merge_sort(0,n-1);
            cout<<cnt<<endl;
    
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4911]: http://acm.hdu.edu.cn/showproblem.php?pid=4911