2

我需要以尽可能低的时间复杂度在所有子数组中找到一些反转计数。
两个元素a[i]并且a[j]形成一个反演 ifa[i] > a[j]和i < j

我已经尝试使用 Fenwick Tree 实现，但超出了时间限制。

我想要一个优化版本的代码：

import java.util.*; 

public class Main { 
static BIT bit; 

static long inversionCountBIT1(int[] arr, int start, 
                                        int end) 
{ 
    bit = new BIT(arr.length); 
    long count = 0; 
    for (int index = start; index >= end; index--) { 
        count += bit.read(arr[index]); 
        bit.update(arr[index], 1); 
    } 
    return count; 
} 

static long inversionCountBIT2(int[] arr, int start, 
                                int end, long val) 
{ 
    bit.update(arr[start + 1], -1);
    int numGreaterThanFirst = start - end - bit.read(arr[start + 1] + 1); 
    long count = val + bit.read(arr[end]) - numGreaterThanFirst; 
    bit.update(arr[end], 1); 

    return count; 
} 

public static long inversionCount(int n, int k, int[] arr) 
{ 
    bit = new BIT(n); 
    HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); 
    int[] asort = arr.clone(); 

    Arrays.sort(asort); 
    int index = 0; 
    int current = 1; 
    for (int i = 0; i < n; i++) { 
        if (!freq.containsKey(asort[i])) { 
            freq.put(asort[i], current); 
            current++; 
        } 
    } 
    for (int i = 0; i < n; i++) { 
        arr[i] = freq.get(arr[i]); 
    } 

    long count = 0; 
    long val = 0; 

    for (int start = n - 1; start >= k - 1; start--) { 
        int end = start - k + 1; 
        if (start == n - 1) { 
            val = inversionCountBIT1(arr, n - 1, n - k); 
        } else { 
            val = inversionCountBIT2(arr, start, end, val); 
        } 
        count += val; 
    } 
    return count; 
} 

public static void main(String[] args) throws Exception 
{   
    Scanner scn  = new Scanner(System.in);
    int t=scn.nextInt() ; 
    int n;
    long k ; 
    while(t>0)
    {  
        n= scn.nextInt()  ; 
        k =scn.nextLong() ; 
        long result = 0; 
    int[] arr =new int[n]; 
    for(int i=0;i<n;i++)
    {
        arr[i]=scn.nextInt() ;
    }
    for(int i=1;i<=n;i++)
    result += inversionCount(n, i, arr); 
    System.out.println(result%k); 
    t--;
} 
}

static class BIT { 
    int[] tree; 
    int maxVal; 
public BIT(int N) 
    { 
        tree = new int[N + 1]; 
        maxVal = N; 
    } 

    void update(int index, int val) 
    { 
        while (index <= maxVal) { 
            tree[index] += val; 
            index += (index & -index); 
        } 
    } 

    int read(int index) 
    { 
        --index; 
        int cumulative_sum = 0; 
        while (index > 0) { 
            cumulative_sum += tree[index]; 
            index -= (index & -index); 
        } 
        return cumulative_sum; 
    } 
}; 
}

超过时间限制

4

1 回答 1

0

首先按降序对数组进行排序，然后遍历树并使用BIT保持所有索引位置的总和，其值大于当前索引处的值，然后将该总和乘以（n-当前索引）。

int main()
{
    memset(bit,0,sizeof(bit));

    long long n;
    sfl(n)

    util arr[n+1];

    f(i,1,n+1)
    {
        sfl(arr[i].val)
        arr[i].idx=i;
    }

    sort(arr+1,arr+n+1,cmp);

    ll ans=0;

    f(i,1,n+1)
    {
        ll temp1=totsum(arr[i].idx);
        ans=(ans+(temp1*(n-arr[i].idx+1))%mod)%mod;
        update(arr[i].idx,arr[i].idx,n);
    }

    pfl(ans)
}
于 2020-01-10T22:30:39.047 回答