Cuente el número de pares con el comparador dado

Dada una array arr[] , la tarea es contar el número de pares (arr[i], arr[j]) a la derecha de cada elemento con cualquier comparador personalizado. 

El comparador puede ser de cualquier tipo, algunos de ellos se detallan a continuación:  

arr[i] > arr[j],    where i < j
arr[i] < arr[j],    where i  2 * arr[j], where i < j

Ejemplos:  

Entrada: arr[] = {5, 4, 3, 2, 1}, comp = arr[i] > arr[j] 
Salida: 10 
Explicación: 
Hay 10 pares de este tipo, en los que el elemento derecho es más pequeño que el elemento izquierdo – 
{(5, 4), (5, 3), (5, 2), (5, 1), (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1)} 

Entrada: arr[] = {3, 4, 3}, comp = arr[i] == arr[j] 
Salida: 1 
Explicación: 
Solo existe un par de elementos tales que son iguales. Eso es (3, 3) 

Solución ingenua: iterar sobre cada par de elementos, de modo que i < j y verificar para cada par si el comparador personalizado es verdadero o no. Si es así, entonces incremente el conteo.
Complejidad del Tiempo: O(N ² )

Enfoque eficiente: la idea es personalizar la ordenación por fusión para calcular dichos pares al momento de fusionar dos subarreglos. Habrá dos tipos de conteo para cada array que sea:  

• Pares entre arreglos: pares que están presentes en el propio subarreglo izquierdo.
• Pares Intra-Array: Pares que están presentes en el subarreglo derecho.

Para los subarreglos izquierdos, el conteo se puede calcular recursivamente de abajo hacia arriba, mientras que la tarea principal será contar los pares dentro del arreglo.

Por lo tanto, el total de dichos pares se puede definir como: 

Total Pairs = Inter-Array pairs in Left Sub-array +
      Inter-Array pairs in Right Sub-array +
      Intra-Array pairs from left to right sub-array 

A continuación se muestra la ilustración de los pares intraarreglo del arreglo desde el subarreglo izquierdo al subarreglo derecho: 

• Caso base: el caso base para este problema será cuando solo haya un elemento en los dos subarreglos y queramos verificar los pares dentro del arreglo. Luego, verifique que esos dos elementos formen uno de esos pares, luego incremente el conteo y también coloque el elemento más pequeño en su posición.

if start1 == end1 and start2 == end2:
    if compare(arr, start1, start2):
        c += 1

• Caso recursivo: este problema se puede dividir en tres tipos sobre la base de la función de comparación: 
  1. Cuando el operador de comparación entre pares es mayor o igual que.
  2. Cuando el operador de comparación entre pares es menor o igual que.
  3. Cuando el operador de comparación entre pares es igual a.

Por lo tanto, estos tres casos se pueden calcular individualmente para tales pares.

• Caso 1: en el caso de que sea mayor o igual que, si encontramos un par así, todos los elementos a la derecha de ese subarreglo también formarán un par con el elemento actual. Debido a lo cual, el recuento de tales pares se incrementa por el número de elementos que quedan en el subconjunto izquierdo.

if compare(arr, start1, start2):
    count += end1 - start1 + 1

• Caso 2: En el caso de que sea menor o igual que, si encontramos un par así, todos los elementos a la derecha de ese subarreglo también formarán un par con el elemento actual. Debido a lo cual, el recuento de dichos pares se incrementa por el número de elementos que quedan en el subconjunto derecho.

if compare(arr, start1, start2):
    count += end2 - start2 + 1

• Caso 3: En caso de que sea igual a, si encontramos algún par, entonces tratamos de encontrar todos los pares posibles en el subarreglo izquierdo con la ayuda de un bucle while . En cada par posible, incremente el conteo en 1.

if compare(arr, start1, start2):
    while compare(arr, start1, start2):
        count += 1
        start1 += 1

• Finalmente, fusione los dos subarreglos como se hace en el ordenamiento por fusión .

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation to find the
// elements on the right with the given
// custom comparator
 
#include <bits/stdc++.h>
 
using namespace std;
 
// comparator to check
// if two elements are equal
bool compare(int arr[], int s1, int s2){
    if (arr[s1] > arr[s2]){
        return true;
    }
    else{
        return false;
    }
}
 
// Function to find the Intra-Array
// Count in the two subarrays
int findIntraArrayCount(int arr[], int s1,
       int e1, int s2, int e2, int g){
            
    // Base Case
    if (s1 == e1 && s2 == e2){
        int c = 0;
        if (compare(arr, s1, s2)){
            c += 1;
        }
        if (arr[s1] > arr[s2]){
            int temp = arr[s1];
            arr[s1] = arr[s2];
            arr[s2] = temp;
        }
        return c;
    }
     
    // Variable for keeping
    // the count of the pair
    int c = 0;
    int s = s1, e = e2, s3 = s1;
    int e3 = e1, s4 = s2, e4 = e2;
     
    while (s1 <= e1 && s2 <= e2){
         
        // Condition when we have to use the
        // Greater than comparator
        if (g == 1){
            if (compare(arr, s1, s2)){
                c += e1 - s1 + 1;
                s2 += 1;
            }
            else{
                s1 += 1;
            }
        }
         
        // Condition when we have to use the
        // Less than comparator
        else if (g == 0){
            if (compare(arr, s1, s2)){
                c += e2 - s2 + 1;
                s1 += 1;
            }
            else {
                s2 += 1;
            }
        }
         
        // Condition when we have to use the
        // Equal to Comparator
        else if (g == -1){
            if (compare(arr, s1, s2)){
                int c1 = 0;
                while (s1 <= e1 &&
                       compare(arr, s1, s2)){
                    c1 += 1;
                    s1 += 1;
                }
                s1 -= 1;
                int c2 = 0;
                while (s2 <= e2 &&
                       compare(arr, s1, s2)){
                    c2 += 1;
                    s2 += 1;
                }
                c += c1 * c2;
            }
            else {
                if (arr[s1] > arr[s2]){
                    s2 += 1;
                }
                else{
                    s1 += 1;
                }
            }
        }
    }
    s1 = s3; e1 = e3;
    s2 = s4; e2 = e4;
     
    // Array to store
    // the sorted subarray
    vector<int> aux;
     
    // Merge the two subarrays
    while (s1 <= e1 && s2 <= e2){
        if (arr[s1] <= arr[s2]){
            aux.push_back(arr[s1]);
            s1 += 1;
        }
        else{
            aux.push_back(arr[s2]);
            s2 += 1;
        }
    }
     
    // Copy subarray 1 elements
    while (s1 <= e1){
        aux.push_back(arr[s1]);
        s1 += 1;
    }
     
    // Copy subarray 2 elements
    while (s2 <= e2){
        aux.push_back(arr[s2]);
        s2 += 1;
    }
     
    // Update the original array
    for (int i = s; i <= e; i++){
        arr[i] = aux[i-s];
    }
    return c;
}
 
// Function to find such pairs with
// any custom comparator function
int findElementsOnRight(int arr[], int s,
                           int e, int g){
    if (s >= e){
        return 0;
    }
    int mid = (s+e)/2;
     
    // Recursive call for inter-array
    // count of pairs in left subarrays
    int c1 = findElementsOnRight(
                      arr, s, mid, g);
     
    // Recursive call for inter-array
    // count of pairs in right sub-arrays
    int c2 = findElementsOnRight(
                   arr, mid + 1, e, g);
     
    // Call for intra-array pairs
    int c3 = findIntraArrayCount(
              arr, s, mid, mid+1, e, g);
     
    return c1 + c2 + c3;
}
 
 
// Driver code
int main()
{
    int arr[] = {4, 3, 2, 1};
    int g = 1;
    cout << findElementsOnRight(arr, 0, 3, g);
    return 0;
}

// Java implementation to find the
// elements on the right with the given
// custom comparator
 
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
     
    // comparator to check
    // if two elements are equal
    public static boolean compare(
          int[] arr, int s1, int s2){
        if (arr[s1] > arr[s2]){
            return true;
        }
        else{
            return false;
        }
    }
     
    // Function to find the Intra-Array
    // Count in the two subarrays
    public static int findIntraArrayCount(
        int[] arr, int s1, int e1, int s2,
                           int e2, int g){
                                
        // Base Case
        if (s1 == e1 && s2 == e2){
            int c = 0;
            if (compare(arr, s1, s2)){
                c += 1;
            }
            if (arr[s1] > arr[s2]){
                int temp = arr[s1];
                arr[s1] = arr[s2];
                arr[s2] = temp;
            }
            return c;
        }
         
        // Variable for keeping
        // the count of the pair
        int c = 0;
        int s = s1, e = e2, s3 = s1;
        int e3 = e1, s4 = s2, e4 = e2;
         
        while (s1 <= e1 && s2 <= e2){
             
            // Condition when we have to use the
            // Greater than comparator
            if (g == 1){
                if (compare(arr, s1, s2)){
                    c += e1 - s1 + 1;
                    s2 += 1;
                }
                else{
                    s1 += 1;
                }
            }
             
            // Condition when we have to use the
            // Equal to Comparator
            else if (g == 0){
                if (compare(arr, s1, s2)){
                    c += e2 - s2 + 1;
                    s1 += 1;
                }
                else {
                    s2 += 1;
                }
            }
             
            // Condition when we have to use the
            // Equal to Comparator
            else if (g == -1){
                if (compare(arr, s1, s2)){
                    int c1 = 0;
                    while (s1 <= e1 &&
                         compare(arr, s1, s2)){
                        c1 += 1;
                        s1 += 1;
                    }
                    s1 -= 1;
                    int c2 = 0;
                    while (s2 <= e2 &&
                          compare(arr, s1, s2)){
                        c2 += 1;
                        s2 += 1;
                    }
                    c += c1 * c2;
                }
                else {
                    if (arr[s1] > arr[s2]){
                        s2 += 1;
                    }
                    else{
                        s1 += 1;
                    }
                }
            }
        }
        s1 = s3; e1 = e3;
        s2 = s4; e2 = e4;
         
        // Array to store
        // the sorted subarray
        ArrayList<Integer> aux =
                     new ArrayList<>();
                      
        // Merge the two subarrays
        while (s1 <= e1 && s2 <= e2){
            if (arr[s1] <= arr[s2]){
                aux.add(arr[s1]);
                s1 += 1;
            }
            else{
                aux.add(arr[s2]);
                s2 += 1;
            }
        }
         
        // Copy subarray 1 elements
        while (s1 <= e1){
            aux.add(arr[s1]);
            s1 += 1;
        }
         
        // Copy subarray 2 elements
        while (s2 <= e2){
            aux.add(arr[s2]);
            s2 += 1;
        }
         
        // Update the original array
        for (int i = s; i <= e; i++){
            arr[i] = aux.get(i-s);
        }
        return c;
    }
     
    // Function to find such pairs with
    // any custom comparator function
    public static int findElementsOnRight(
        int[] arr, int s, int e, int g){
        if (s >= e){
            return 0;
        }
        int mid = (s+e)/2;
         
        // Recursive call for inter-array
        // count of pairs in left subarrays
        int c1 = findElementsOnRight(arr, s,
                                     mid, g);
         
        // Recursive call for inter-array
        // count of pairs in right sub-arrays
        int c2 = findElementsOnRight(arr, mid + 1,
                                         e, g);
         
        // Call for intra-array pairs
        int c3 = findIntraArrayCount(arr, s,
                            mid, mid+1, e, g);
         
        return c1 + c2 + c3;                                  
    }
     
    // Driver code
    public static void main (String[] args) {
        int[] arr = {4, 3, 2, 1};
        int g = 1;
        System.out.println(
            findElementsOnRight(arr, 0, 3, g));
    }
}

# Python3 implementation to find the
# elements on the right with the given
# custom comparator
 
import random, math
from copy import deepcopy as dc
 
# comparator to check
# if two elements are equal
def compare(arr, s1, s2):
    if arr[s1] > arr[s2]:
        return True
    else:
        return False
 
 
# Function to find the Intra-Array
# Count in the two subarrays
def findIntraArrayCount(arr, s1, \
                e1, s2, e2, g):
     
    # Base Case
    if s1 == e1 and s2 == e2:
        c = 0
        if compare(arr, s1, s2):
            c += 1
        if arr[s1] > arr[s2]:
            arr[s1], arr[s2] = arr[s2], arr[s1]
        return c
 
 
    # Variable for keeping
    # the count of the pair
    c = 0
     
    # Total subarray length
    s = dc(s1); e = dc(e2)
     
    # length of subarray 1
    s3 = dc(s1); e3 = dc(e1)
     
    # length of subarray 2
    s4 = dc(s2); e4 = dc(e2)
     
    while s1 <= e1 and s2 <= e2:
 
 
        # Condition when we have to use the
        # Greater than comparator
        if g == 1:
            if compare(arr, s1, s2):
                c += e1 - s1 + 1
                s2 += 1
            else:
                s1 += 1
 
        # Condition when we have to use the
        # Less than comparator
        elif g == 0:
            if compare(arr, s1, s2):
                c += e2 - s2 + 1
                s1 += 1
            else:
                s2 += 1
                 
        # Condition when we have to use the
        # Equal to Comparator
        elif g == -1:
            if compare(arr, s1, s2):
                c1 = 0
                while s1 <= e1 and\
                   compare(arr, s1, s2):
                    c1 += 1
                    s1 += 1
                s1 -= 1
                c2 = 0
                while s2 <= e2 and\
                    compare(arr, s1, s2):
                    c2 += 1
                    s2 += 1
                c += c1 * c2
            else:
                if arr[s1] > arr[s2]:
                    s2 += 1
                else:
                    s1 += 1
 
    s1 = dc(s3); e1 = dc(e3)
     
    s2 = dc(s4); e2 = dc(e4)
     
    # Array to store the sorted subarray
    aux = []
     
     
    # Merge the two subarrays
    while s1 <= e1 and s2 <= e2:
        if arr[s1] <= arr[s2]:
            aux.append(arr[s1])
            s1 += 1
        else:
            aux.append(arr[s2])
            s2 += 1
     
    # Copy subarray 1 elements
    while s1 <= e1:
        aux.append(arr[s1])
        s1 += 1
         
     
    # Copy subarray 2 elements
    while s2 <= e2:
        aux.append(arr[s2])
        s2 += 1
         
     
    # Update the original array
    for i in range(s, e + 1):
        arr[i] = aux[i-s]
    return c
 
 
 
# Function to find such pairs with
# any custom comparator function
def findElementsOnRight(arr, s, e, g):
    if s >= e:
        return 0
    mid = (s + e)//2
     
    # Recursive call for inter-array
    # count of pairs in left subarrays
    c1 = findElementsOnRight(arr, s, \
                            mid, g)
     
    # Recursive call for inter-array
    # count of pairs in right sub-arrays
    c2 = findElementsOnRight(arr, mid + 1, \
                                e, g)
     
    # Call for intra-array pairs
    c3 = findIntraArrayCount(arr, s, mid, \
                            mid + 1, e, g)
    return c1 + c2 + c3
 
 
 
 
# Driver Code
if __name__ == "__main__":
    arr = [4, 3, 2, 1]
    g = 1
    out = findElementsOnRight(arr, 0, \
                        len(arr)-1, g)
    print(out)

// C# implementation to find the 
// elements on the right with the
// given custom comparator 
using System;
using System.Collections.Generic;
 
class GFG{
     
// comparator to check 
// if two elements are equal 
public static bool compare(int[] arr, int s1,
                                      int s2)
{
    if (arr[s1] > arr[s2])
    {
        return true;
    }
    else
    {
        return false;
    }
}
   
// Function to find the Intra-Array 
// Count in the two subarrays 
public static int findIntraArrayCount(int[] arr, int s1,
                                      int e1, int s2, 
                                      int e2, int g)
{
     
    // Base Case
    if (s1 == e1 && s2 == e2)
    {
        int cc = 0;
        if (compare(arr, s1, s2))
        {
            cc += 1;
        }
        if (arr[s1] > arr[s2])
        {
            int temp = arr[s1];
            arr[s1] = arr[s2];
            arr[s2] = temp;
        }
        return cc;
    }
       
    // Variable for keeping 
    // the count of the pair
    int c = 0;
    int s = s1, e = e2, s3 = s1;
    int e3 = e1, s4 = s2, e4 = e2;
       
    while (s1 <= e1 && s2 <= e2)
    {
         
        // Condition when we have to use the 
        // Greater than comparator
        if (g == 1)
        {
            if (compare(arr, s1, s2))
            {
                c += e1 - s1 + 1;
                s2 += 1;
            }
            else
            {
                s1 += 1;
            }
        }
           
        // Condition when we have to use the 
        // Equal to Comparator 
        else if (g == 0)
        {
            if (compare(arr, s1, s2))
            {
                c += e2 - s2 + 1;
                s1 += 1;
            }
            else
            {
                s2 += 1;
            }
        }
           
        // Condition when we have to use the 
        // Equal to Comparator 
        else if (g == -1)
        {
            if (compare(arr, s1, s2))
            {
                int c1 = 0;
                while (s1 <= e1 && 
                       compare(arr, s1, s2))
                {
                    c1 += 1;
                    s1 += 1;
                }
                s1 -= 1;
                int c2 = 0;
                while (s2 <= e2 && 
                       compare(arr, s1, s2))
                {
                    c2 += 1;
                    s2 += 1;
                }
                c += c1 * c2;
            }
            else
            {
                if (arr[s1] > arr[s2])
                {
                    s2 += 1;
                }
                else
                {
                    s1 += 1;
                }
            }
        }
    }
    s1 = s3; e1 = e3;
    s2 = s4; e2 = e4;
       
    // Array to store 
    // the sorted subarray
    List<int> aux = new List<int>();
                    
    // Merge the two subarrays
    while (s1 <= e1 && s2 <= e2)
    {
        if (arr[s1] <= arr[s2])
        {
            aux.Add(arr[s1]);
            s1 += 1;
        }
        else
        {
            aux.Add(arr[s2]);
            s2 += 1;
        }
    }
       
    // Copy subarray 1 elements 
    while (s1 <= e1)
    {
        aux.Add(arr[s1]);
        s1 += 1;
    }
       
    // Copy subarray 2 elements
    while (s2 <= e2)
    {
        aux.Add(arr[s2]);
        s2 += 1;
    }
       
    // Update the original array
    for(int i = s; i <= e; i++)
    {
        arr[i] = aux[i-s];
    }
    return c;
}
   
// Function to find such pairs with 
// any custom comparator function 
public static int findElementsOnRight(int[] arr, int s,
                                      int e, int g)
{
    if (s >= e)
    {
        return 0;
    }
    int mid = (s + e) / 2;
       
    // Recursive call for inter-array 
    // count of pairs in left subarrays
    int c1 = findElementsOnRight(arr, s, 
                                 mid, g);
       
    // Recursive call for inter-array 
    // count of pairs in right sub-arrays 
    int c2 = findElementsOnRight(arr, mid + 1, 
                                   e, g);
       
    // Call for intra-array pairs 
    int c3 = findIntraArrayCount(arr, s, mid,
                                 mid + 1, e, g);
       
    return c1 + c2 + c3;                                   
}
 
// Driver code
static public void Main()
{
    int[] arr = { 4, 3, 2, 1 };
    int g = 1;
     
    Console.WriteLine(findElementsOnRight(
        arr, 0, 3, g));
}
}
 
// This code is contributed by offbeat

<script>
// Javascript implementation to find the
// elements on the right with the given
// custom comparator
 
 
// comparator to check
// if two elements are equal
function compare(arr, s1, s2) {
    if (arr[s1] > arr[s2]) {
        return true;
    }
    else {
        return false;
    }
}
 
// Function to find the Intra-Array
// Count in the two subarrays
function findIntraArrayCount(arr, s1, e1, s2, e2, g) {
 
    // Base Case
    if (s1 == e1 && s2 == e2) {
        let c = 0;
        if (compare(arr, s1, s2)) {
            c += 1;
        }
        if (arr[s1] > arr[s2]) {
            let temp = arr[s1];
            arr[s1] = arr[s2];
            arr[s2] = temp;
        }
        return c;
    }
 
    // Variable for keeping
    // the count of the pair
    let c = 0;
    let s = s1, e = e2, s3 = s1;
    let e3 = e1, s4 = s2, e4 = e2;
 
    while (s1 <= e1 && s2 <= e2) {
 
        // Condition when we have to use the
        // Greater than comparator
        if (g == 1) {
            if (compare(arr, s1, s2)) {
                c += e1 - s1 + 1;
                s2 += 1;
            }
            else {
                s1 += 1;
            }
        }
 
        // Condition when we have to use the
        // Less than comparator
        else if (g == 0) {
            if (compare(arr, s1, s2)) {
                c += e2 - s2 + 1;
                s1 += 1;
            }
            else {
                s2 += 1;
            }
        }
 
        // Condition when we have to use the
        // Equal to Comparator
        else if (g == -1) {
            if (compare(arr, s1, s2)) {
                let c1 = 0;
                while (s1 <= e1 &&
                    compare(arr, s1, s2)) {
                    c1 += 1;
                    s1 += 1;
                }
                s1 -= 1;
                let c2 = 0;
                while (s2 <= e2 &&
                    compare(arr, s1, s2)) {
                    c2 += 1;
                    s2 += 1;
                }
                c += c1 * c2;
            }
            else {
                if (arr[s1] > arr[s2]) {
                    s2 += 1;
                }
                else {
                    s1 += 1;
                }
            }
        }
    }
    s1 = s3; e1 = e3;
    s2 = s4; e2 = e4;
 
    // Array to store
    // the sorted subarray
    let aux = new Array();
 
    // Merge the two subarrays
    while (s1 <= e1 && s2 <= e2) {
        if (arr[s1] <= arr[s2]) {
            aux.push(arr[s1]);
            s1 += 1;
        }
        else {
            aux.push(arr[s2]);
            s2 += 1;
        }
    }
 
    // Copy subarray 1 elements
    while (s1 <= e1) {
        aux.push(arr[s1]);
        s1 += 1;
    }
 
    // Copy subarray 2 elements
    while (s2 <= e2) {
        aux.push(arr[s2]);
        s2 += 1;
    }
 
    // Update the original array
    for (let i = s; i <= e; i++) {
        arr[i] = aux[i - s];
    }
    return c;
}
 
// Function to find such pairs with
// any custom comparator function
function findElementsOnRight(arr, s, e, g) {
    if (s >= e) {
        return 0;
    }
    let mid = Math.floor((s + e) / 2);
 
    // Recursive call for inter-array
    // count of pairs in left subarrays
    let c1 = findElementsOnRight(
        arr, s, mid, g);
 
    // Recursive call for inter-array
    // count of pairs in right sub-arrays
    let c2 = findElementsOnRight(
        arr, mid + 1, e, g);
 
    // Call for intra-array pairs
    let c3 = findIntraArrayCount(
        arr, s, mid, mid + 1, e, g);
 
    return c1 + c2 + c3;
}
 
 
// Driver code
 
let arr = [4, 3, 2, 1];
let g = 1;
document.write(findElementsOnRight(arr, 0, 3, g));
 
 
// This code is contributed by gfgking
</script>

6

Complejidad del tiempo: el método anterior toma el tiempo O (N * logN).
Espacio Auxiliar: O(N)