fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.lang.Math;
  4.  
  5.  class Solution {
  6.     // Fenwick / Binary Indexed Tree for frequencies
  7.     static class Fenwick {
  8.         int n;
  9.         int[] bit;
  10.         Fenwick(int n) {
  11.             this.n = n;
  12.             bit = new int[n+1];
  13.         }
  14.         void add(int idx, int delta) {
  15.             for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
  16.         }
  17.         int sum(int idx) {
  18.             int s = 0;
  19.             for (; idx > 0; idx -= idx & -idx) s += bit[idx];
  20.             return s;
  21.         }
  22.         // sum in [l, r]
  23.         int rangeSum(int l, int r) {
  24.             if (r < l) return 0;
  25.             return sum(r) - sum(l-1);
  26.         }
  27.     }
  28.  
  29.     public static int permInv(int n, List<Integer> A, int k) {
  30.         // convert to 1-based int array for convenience
  31.         int[] arr = new int[n];
  32.         for (int i = 0; i < n; ++i) arr[i] = A.get(i);
  33.  
  34.         // 1) compute initial total inversions using Fenwick on values 1..n
  35.         Fenwick fwAll = new Fenwick(n);
  36.         long initialInv = 0;
  37.         for (int i = 0; i < n; ++i) {
  38.             int v = arr[i];
  39.             int leq = fwAll.sum(v);           // number <= v already seen
  40.             int greaterBefore = i - leq;      // how many seen elements > v
  41.             initialInv += greaterBefore;
  42.             fwAll.add(v, 1);
  43.         }
  44.  
  45.         // If k == 1, reversing does nothing (pairs_inside = 0), return initial inv.
  46.         if (k <= 1) return (int) initialInv;
  47.  
  48.         long pairsInside = (long)k * (k - 1) / 2;
  49.  
  50.         // 2) compute internal inversions for first window [0..k-1]
  51.         Fenwick fwWindow = new Fenwick(n); // counts of values currently in window
  52.         long windowInv = 0;
  53.         int currentWindowSize = 0;
  54.         for (int j = 0; j < k; ++j) {
  55.             int v = arr[j];
  56.             int leq = fwWindow.sum(v);          // <= v among already inserted (earlier in window)
  57.             int greater = currentWindowSize - leq;
  58.             windowInv += greater;
  59.             fwWindow.add(v, 1);
  60.             currentWindowSize++;
  61.         }
  62.  
  63.         long best = Math.min(initialInv, initialInv + pairsInside - 2 * windowInv);
  64.  
  65.         // Slide window: for i from 1 to n-k
  66.         for (int i = 1; i <= n - k; ++i) {
  67.             int leftVal = arr[i-1];            // element leaving window
  68.             // number of elements less than leftVal in current window (these were inversions contributed by leftVal)
  69.             int lessThanLeft = fwWindow.sum(leftVal - 1);
  70.             windowInv -= lessThanLeft;        // remove its inversion contributions
  71.             // remove leftVal from fenwick
  72.             fwWindow.add(leftVal, -1);
  73.             currentWindowSize--;
  74.  
  75.             int newVal = arr[i + k - 1];      // element entering window
  76.             int leqNew = fwWindow.sum(newVal); // number <= newVal among current elements
  77.             int greaterNew = currentWindowSize - leqNew;
  78.             windowInv += greaterNew;          // inversions added by placing newVal at the end
  79.             fwWindow.add(newVal, 1);
  80.             currentWindowSize++;
  81.  
  82.             long newTotal = initialInv + pairsInside - 2 * windowInv;
  83.             if (newTotal < best) best = newTotal;
  84.         }
  85.  
  86.         return (int) best;
  87.     }
  88.  
  89.     public static void main(String[] args) {
  90.         Scanner scan = new Scanner(System.in);
  91.         int n = Integer.parseInt(scan.nextLine().trim());
  92.         List<Integer> A = new ArrayList<>(n);
  93.         for (int j = 0; j < n; j++) {
  94.             A.add(Integer.parseInt(scan.nextLine().trim()));
  95.         }
  96.         int k = Integer.parseInt(scan.nextLine().trim());
  97.         int result = permInv(n, A, k);
  98.         System.out.println(result);
  99.     }
  100. }
Success #stdin #stdout 0.17s 54492KB
comments (?)
stdin
copy 
5
1
4
2
3
5
3
stdout
copy 
1
https://ideone.com/7Hl0FR
language:
Java (HotSpot 12)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!