Contar trillizos (i, j, k) en una array de elementos distintos tal que a[i] < a[j] > a[k] e i < j < k

Dada una array arr[] que consta de N enteros distintos, la tarea es contar el número de tripletes (i, j, k) posibles de la array arr[] tales que i < j < k y arr[i] < arr[ j] > arr[k] .

Ejemplos:

Entrada: arr[] = {2, 3, 1, -1}
Salida: 2
Explicación: De la array dada, todos los tripletes posibles que satisfacen la propiedad (i, j, k) y arr[i] < arr[j] > arr[k] son:

1. (0, 1, 2): array[0](= 2) < array[1](= 3) > array[2](= 1).
2. (0, 1, 3): array[0](= 2) < array[1](= 3) > array[3](= -1).

Por lo tanto, la cuenta de trillizos es 2.

Entrada: arr[] = {2, 3, 4, 6, 7, 9, 1, 12, 10, 8}
Salida: 41

Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array dada y para cada elemento arr[i] , el producto del conteo de elementos más pequeños en el lado izquierdo de arr[i] y el conteo de elementos más pequeños en el lado izquierdo. el lado derecho de arr[i] da el conteo de tripletes para el elemento arr[i] como elemento central. La suma de todos los conteos obtenidos para cada índice es el número requerido de tripletes válidos.
Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar al encontrar el recuento de elementos más pequeños utilizando una estructura de datos basada en políticas ( PBDS) . Siga los pasos a continuación para resolver el problema:

• Inicialice la variable, digamos ans a 0 que almacena el número total de pares posibles.
• Inicialice dos contenedores de la estructura de datos basada en políticas , digamos P y Q.
• Inicializar un vector de pares V , donde V[i]. primero y V[i].segundo almacena el recuento de elementos más pequeños en el lado izquierdo y derecho de cada elemento de array arr[i] .
• Recorra la array dada y para cada elemento arr[i] , actualice el valor de V[i] .primero como P.order_of_key(arr[i]) e inserte arr[i] para establecer P .
• Recorra la array de derecha a izquierda y para cada elemento arr[i] , actualice el valor de V[i] .primero como P.order_of_key(arr[i]) e inserte arr[i] para establecer Q .
• Recorra el vector de pares V y agregue el valor de V[i].primero * V[i].segundo a la variable ans .
• Después de completar los pasos anteriores, imprima el valor de ans como el número total de pares.

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

// C++ program for the above approach
  
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
  
// Function to find the count of triplets
// satisfying the given conditions
void findTriplets(int arr[], int n)
{
    // Stores the total count of pairs
    int ans = 0;
  
    // Declare the set
    tree<int, null_type, less<int>, rb_tree_tag,
         tree_order_statistics_node_update>
        p, q;
  
    // Declare the vector of pairs
    vector<pair<int, int> > v(n);
  
    // Iterate over the array from
    // left to right
    for (int i = 0; i < n; i++) {
  
        // Find the index of element
        // in sorted array
        int index = p.order_of_key(arr[i]);
  
        // Assign to the left
        v[i].first = index;
  
        // Insert into the set
        p.insert(arr[i]);
    }
  
    // Iterate from right to left
    for (int i = n - 1; i >= 0; i--) {
  
        // Find the index of element
        // in the sorted array
        int index = q.order_of_key(arr[i]);
  
        // Assign to the right
        v[i].second = index;
  
        // Insert into the set
        q.insert(arr[i]);
    }
  
    // Traverse the vector of pairs
    for (int i = 0; i < n; i++) {
        ans += (v[i].first * v[i].second);
    }
  
    // Print the total count
    cout << ans;
}
  
// Driver Code
int main()
{
    int arr[] = { 2, 3, 1, -1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    findTriplets(arr, N);
  
    return 0;
}

2

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)