逆序对数变形

Problem Description Recall the problem of finding the number of inversions. As in the course, we are given a sequence of nn numbers a1,a2,⋯,ana1,a2,⋯,an, and we define an inversion to be a pair i<jiajai>aj.

We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let’s call a pair a significant inversion if i<ji3ajai>3aj. Give an O(nlogn)O(nlog⁡n) algorithm to count the number of significant inversions between two orderings.

The array contains N elements (1<=N<=100,000). All elements are in the range from 1 to 1,000,000,000.

Input The first line contains one integer N, indicating the size of the array. The second line contains N elements in the array.

50% test cases guarantee that N < 1000. Output Output a single integer which is the number of pairs of significant inversions.

Sample Inout 6 13 8 5 3 2 1 Sample Output 6 解法:标准的逆序对数上加了一点变化，ai>aj*3 才算做逆序对数，因此在merge之前扫一遍就行计算逆序对的数量，然后加起来，将merge与计算逆序对数分开。 代码：

#include<algorithm>
using  namespace std;
long long t[100010];
long long  a[100010];
long long sum=0;
void solve(int l,int r)
{
    //printf("%d %d\n",l,r);
    if(r-l<2)
    {
        if(r - l == 1 && a[l] > 3 * a[r])
            sum++;
        if(r-l  ==  1 &&  a[l] > a[r]){
            swap(a[l], a[r]);
        }
        return ;
    }
    int m = (l + r) >> 1;
    solve(l , m);
    solve(m+1 , r);
    int now  = m-l+1;
    int sz = l, sy = m+1;
    int i = m, j = r;
   while (i >= l && j > m) {
       if(a[i] > (long long) 3 * a[j]) { 
           sum += j - m;
           i--;
       }else{
           j--;
       }
   }
    for(int i = 0; i < r - l + 1; i++)
    {   
        if(sz <= m && sy <= r)
            {
                if(a[sz] > a[sy]){
                    t[i] = a[sy];
                    sy++; 
                    //sum += now;
                }
                else
                {
                    t[i] = a[sz];
                    sz++; 
                    now--;
                }
            }
        else if(sz == m+1)
        {
            while(sy <= r)
            {
                t[i] = a[sy];
                sy++; i++;
            }
        }
        else
        {
            while(sz <= m)
            {
                t[i] = a[sz];
                sz++;
                i++;
            }
        }
    }
    for(int i= l ; i <= r; i++)
        a[i] = t[i-l];
   
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <=n; i++)
        scanf("%lld",&a[i]);
    solve(1,n);
    printf("%lld\n",sum);
    return 0;
}