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.         Fenwick fwAll = new Fenwick(n);
  35.         long initialInv = 0;
  36.         for (int i = 0; i < n; ++i) {
  37.             int v = arr[i];
  38.             int leq = fwAll.sum(v);           
  39.             int greaterBefore = i - leq;      
  40.             initialInv += greaterBefore;
  41.             fwAll.add(v, 1);
  42.         }
  43.  
  44.         if (k <= 1) return (int) initialInv;
  45.  
  46.         long pairsInside = (long)k * (k - 1) / 2;
  47.  
  48.         Fenwick fwWindow = new Fenwick(n); 
  49.         long windowInv = 0;
  50.         int currentWindowSize = 0;
  51.         for (int j = 0; j < k; ++j) {
  52.             int v = arr[j];
  53.             int leq = fwWindow.sum(v);          // <= v among already inserted (earlier in window)
  54.             int greater = currentWindowSize - leq;
  55.             windowInv += greater;
  56.             fwWindow.add(v, 1);
  57.             currentWindowSize++;
  58.         }
  59.  
  60.         long best = Math.min(initialInv, initialInv + pairsInside - 2 * windowInv);
  61.  
  62.         // Slide window: for i from 1 to n-k
  63.         for (int i = 1; i <= n - k; ++i) {
  64.             int leftVal = arr[i-1];            // element leaving window
  65.             // number of elements less than leftVal in current window (these were inversions contributed by leftVal)
  66.             int lessThanLeft = fwWindow.sum(leftVal - 1);
  67.             windowInv -= lessThanLeft;        // remove its inversion contributions
  68.             // remove leftVal from fenwick
  69.             fwWindow.add(leftVal, -1);
  70.             currentWindowSize--;
  71.  
  72.             int newVal = arr[i + k - 1];      // element entering window
  73.             int leqNew = fwWindow.sum(newVal); // number <= newVal among current elements
  74.             int greaterNew = currentWindowSize - leqNew;
  75.             windowInv += greaterNew;          // inversions added by placing newVal at the end
  76.             fwWindow.add(newVal, 1);
  77.             currentWindowSize++;
  78.  
  79.             long newTotal = initialInv + pairsInside - 2 * windowInv;
  80.             if (newTotal < best) best = newTotal;
  81.         }
  82.  
  83.         return (int) best;
  84.     }
  85.  
  86.     public static void main(String[] args) {
  87.         Scanner scan = new Scanner(System.in);
  88.         int n = Integer.parseInt(scan.nextLine().trim());
  89.         List<Integer> A = new ArrayList<>(n);
  90.         for (int j = 0; j < n; j++) {
  91.             A.add(Integer.parseInt(scan.nextLine().trim()));
  92.         }
  93.         int k = Integer.parseInt(scan.nextLine().trim());
  94.         int result = permInv(n, A, k);
  95.         System.out.println(result);
  96.     }
  97. }
Success #stdin #stdout 0.11s 54644KB
comments (?)
stdin
copy 
5
4
3
5
1
2
2
stdout
copy 
6
https://ideone.com/rujrus
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!