Encuentre el número de subarreglos en la permutación de los primeros N números naturales tales que su mediana sea M

Dada una array arr[] que contiene la permutación de los primeros N números naturales y un entero M ≤ N . La tarea es encontrar el número de subarreglos tales que la mediana de la secuencia sea M. 
La mediana de una secuencia es el valor del elemento que está en el medio de la secuencia después de clasificarlo en orden no decreciente. Si la longitud de la secuencia es par, se utiliza la izquierda de dos elementos intermedios.
 

Ejemplos:  

Entrada: a[] = { 2, 4, 5, 3, 1}, M = 4 
Salida: 4 
Las subarreglas requeridas son {2, 4, 5}, {4}, {4, 5} y {4 , 5, 3}.
 

Entrada: a[] = { 1, 2, 3, 4, 5}, M = 5 
Salida: 1 

Enfoque: El segmento p[l..r] tiene una mediana igual a M si y solo si M le pertenece y menos = mayor o menos = mayor – 1, donde menor es el número de elementos en p[l..r] que son estrictamente menores que M y mayor es un número de elementos en p[l..r] que son estrictamente mayores que M. Aquí hemos usado el hecho de que p es una permutación (en p[l..r] hay es exactamente una aparición de M).
En otras palabras, M pertenece a p[l..r], y el valor mayor – menor es igual a 0 o 1.
Calcula sumas de prefijos suma[0..n], donde suma[i] el valor mayor-menoren el prefijo de la longitud i (es decir, en el subarreglo p[0..i-1]). Para el valor fijo r es fácil calcular el número de tan l que p[l..r] es adecuado. Primero, compruebe que M se encontró en [0..r]. Los valores válidos l son índices tales que: no M en [0..l-1] y sum[l]=sum[r] o sum[r]=sum[l]+1.
Mantengamos un número de sumas de prefijos sum[i] a la izquierda de M para cada valor. Podemos simplemente usar un mapa c, donde c[s] es un número de índices l que sum[l]=s y l están a la izquierda de m.
Entonces, para cada r que p[0..r] contiene m, haz ans += c[sum] + c[sum – 1], donde sum es el valor actual mayor-menor .
A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of sub-arrays
// in the given permutation of first n natural
// numbers such that their median is m
int segments(int n, int p[], int m)
{
    map<int, int> c;
    c[0] = 1;
    bool has = false;
    int sum = 0;
    long long ans = 0;
    for (int r = 0; r < n; r++) {
 
        // If element is less than m
        if (p[r] < m)
            sum--;
 
        // If element greater than m
        else if (p[r] > m)
            sum++;
 
        // If m is found
        if (p[r] == m)
            has = true;
 
        // Count the answer
        if (has)
            ans += c[sum] + c[sum - 1];
 
        // Increment sum
        else
            c[sum]++;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { 2, 4, 5, 3, 1 };
    int n = sizeof(a) / sizeof(a[0]);
    int m = 4;
    cout << segments(n, a, m);
 
    return 0;
}

// Java implementation of the approach
import java.util.HashMap;
 
class GFG
{
 
    // Function to return the count of sub-arrays
    // in the given permutation of first n natural
    // numbers such that their median is m
    public static int segments(int n, int[] p, int m)
    {
        HashMap<Integer, Integer> c = new HashMap<>();
        c.put(0, 1);
        boolean has = false;
        int sum = 0;
        int ans = 0;
        for (int r = 0; r < n; r++)
        {
 
            // If element is less than m
            if (p[r] < m)
                sum--;
 
            // If element greater than m
            else if (p[r] > m)
                sum++;
 
            // If m is found
            if (p[r] == m)
                has = true;
 
            // Count the answer
            if (has)
                ans += (c.get(sum) == null ? 0 :
                        c.get(sum)) +
                       (c.get(sum - 1) == null ? 0 :
                        c.get(sum - 1));
 
            // Increment sum
            else
                c.put(sum, c.get(sum) == null ? 1 :
                           c.get(sum) + 1);
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] a = { 2, 4, 5, 3, 1 };
        int n = a.length;
        int m = 4;
        System.out.println(segments(n, a, m));
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 implementation of the approach
 
# Function to return the count of sub-arrays
# in the given permutation of first n natural
# numbers such that their median is m
def segments(n, p, m):
 
    c = dict()
 
    c[0] = 1
 
    has = False
 
    Sum = 0
 
    ans = 0
 
    for r in range(n):
 
        # If element is less than m
        if (p[r] < m):
            Sum -= 1
 
        # If element greater than m
        elif (p[r] > m):
            Sum += 1
 
        # If m is found
        if (p[r] == m):
            has = True
 
        # Count the answer
        if (has):
            if(Sum in c.keys()):
                ans += c[Sum]
            if Sum-1 in c.keys():
                ans += c[Sum - 1]
 
        # Increment Sum
        else:
            c[Sum] = c.get(Sum, 0) + 1
 
    return ans
 
# Driver code
a = [2, 4, 5, 3, 1]
n = len(a)
m = 4
print(segments(n, a, m))
 
# This code is contributed by mohit kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;            
 
class GFG
{
 
    // Function to return the count of sub-arrays
    // in the given permutation of first n natural
    // numbers such that their median is m
    public static int segments(int n, int[] p, int m)
    {
        Dictionary<int, int> c = new Dictionary<int, int>();
        c.Add(0, 1);
        bool has = false;
        int sum = 0;
        int ans = 0;
        for (int r = 0; r < n; r++)
        {
 
            // If element is less than m
            if (p[r] < m)
                sum--;
 
            // If element greater than m
            else if (p[r] > m)
                sum++;
 
            // If m is found
            if (p[r] == m)
                has = true;
 
            // Count the answer
            if (has)
                ans += (!c.ContainsKey(sum) ? 0 :
                         c[sum]) +
                    (!c.ContainsKey(sum - 1) ? 0 :
                      c[sum - 1]);
 
            // Increment sum
            else
                c.Add(sum, !c.ContainsKey(sum) ? 1 :
                            c[sum] + 1);
        }
        return ans;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] a = { 2, 4, 5, 3, 1 };
        int n = a.Length;
        int m = 4;
        Console.WriteLine(segments(n, a, m));
    }
}
 
// This code is contributed by 29AjayKumar

<?php
// PHP implementation of the approach
 
// Function to return the count of sub-arrays
// in the given permutation of first n natural
// numbers such that their median is m
function segments($n, $p, $m)
{
    $c = array();
    $c[0] = 1;
     
    $has = false;
    $sum = 0;
    $ans = 0;
     
    for ($r = 0; $r < $n; $r++)
    {
 
        // If element is less than m
        if ($p[$r] < $m)
            $sum--;
 
        // If element greater than m
        else if ($p[$r] > $m)
            $sum++;
 
        // If m is found
        if ($p[$r] == $m)
            $has = true;
 
        // Count the answer
        if ($has)
            $ans += $c[$sum] + $c[$sum - 1];
 
        // Increment sum
        else
            $c[$sum]++;
    }
 
    return $ans;
}
 
// Driver code
$a = array( 2, 4, 5, 3, 1 );
$n = count($a);
$m = 4;
 
echo segments($n, $a, $m);
 
// This code is contributed by Ryuga
?>

<script>
 
// javascript implementation of the approach
 
// Function to return the count of sub-arrays
// in the given permutation of first n natural
// numbers such that their median is m
function segments(n, p, m)
{
    var c = new Map();
    c.set(0,1);
    var hs = false;
    var sum = 0;
    var ans = 0;
    var r;
    for (r = 0; r < n; r++) {
 
        // If element is less than m
        if (p[r] < m)
            sum--;
 
        // If element greater than m
        else if (p[r] > m)
            sum++;
 
        // If m is found
        if (p[r] == m)
            hs = true;
 
        // Count the answer
        if (hs){
            if(c.has(sum) && c.has(sum-1))
              ans += c.get(sum) + c.get(sum - 1);
            else if(c.has(sum))
              ans += c.get(sum);
            else if(c.has(sum-1))
             ans += c.get(sum-1);
        }
 
        // Increment sum
        else{
            if(c.has(sum))
             c.set(sum,c.get(sum)+1);
            else
              c.set(sum,1);
        }
    }
 
    return ans;
}
 
// Driver code
 
    var a = [2, 4, 5, 3, 1];
    var n = a.length;
    var m = 4;
    document.write(segments(n, a, m));
 
</script>

4

Complejidad temporal: O(N)
Espacio auxiliar: O(N)