Consultas sobre inserción de un elemento en una Secuencia Bitónica

Dada una secuencia bitónica ‘S’ y ‘Q’ no. de consultas Cada consulta contiene un número entero x _i , 1 <= i <= Q. La tarea es imprimir la longitud de la secuencia bitónica después de insertar el número entero para cada consulta. Además, imprima la secuencia bitónica después de todas las consultas.
Ejemplos: 
 

Entrada: S = { 1, 2, 5, 2 }, Q = 4, x = { 5, 1, 3, 2 } 
Salida: 
4 
5 
6 
6 
Secuencia bitónica: 1 2 3 5 2 1
Explicación: 
 

• Para la primera consulta, necesitamos insertar x ₁ = 5, pero dado que 5 es el elemento máximo y solo podemos tener una aparición del elemento máximo en S, no insertaremos 5 en S. Por lo tanto, tamaño = 4.
• Para la segunda consulta, necesitamos insertar x ₂ = 1, por lo que lo insertamos en la parte decreciente ya que la parte creciente ya tiene 1. Por lo tanto, tamaño = 5.
• Para la tercera consulta, insertamos x ₃ = 3 en el lado creciente para que el tamaño sea 6.
• Para la cuarta consulta, no podemos insertar x ₂ = 2 ya que 2 está tanto en el lado creciente como en el decreciente.

Entrada: S = { 1, 2, 5, 2 }, Q = 4, x = { 5, 6, 4, 4 } 
Salida: 
4 
5 
6 
7 
Secuencia bitónica: 1 2 4 5 6 4 2 
 

Planteamiento: La idea es hacer dos conjuntos, uno de secuencia creciente y otro de secuencia decreciente. 
 

1. Ahora, para cada consulta, primero verifique si x _i es mayor que el elemento máximo en la secuencia bitónica o no.
2. En caso afirmativo, actualice la secuencia máxima e incluya ese elemento en el conjunto para secuencia creciente.
3. De lo contrario, verifique si ese elemento está presente en el conjunto de secuencias crecientes, si no lo incluye en el conjunto de secuencias crecientes, de lo contrario, inclúyalo en el conjunto de secuencias decrecientes.

A continuación se muestra la implementación de este enfoque: 
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the bitonic sequence
void solveQuery(int a[], int n, int x[], int q)
{
    int maxx = INT_MIN;
 
    // Finding the maximum element
    for (int i = 0; i < n; i++)
        maxx = max(maxx, a[i]);
 
    set<int> s1, s2;
 
    s1.insert(a[0]);
    s2.insert(a[n - 1]);
 
    // set to include increasing sequence element
    for (int i = 1; i < n; i++)
        if (a[i] > a[i - 1])
            s1.insert(a[i]);
 
    // set to include decreasing sequence element
    for (int i = n - 2; i >= 0; i--)
        if (a[i] > a[i + 1])
            s2.insert(a[i]);
 
    // removing maximum element from
    // decreasing sequence set
    s2.erase(s2.find(maxx));
 
    // for each query
    for (int i = 0; i < q; i++) {
 
        // checking if x is greater than
        // maximum element or not.
        if (maxx <= x[i]) {
            maxx = x[i];
            s1.insert(x[i]);
        }
 
        else {
 
            // checking if x lie in increasing sequence
            if (s1.find(x[i]) == s1.end())
                s1.insert(x[i]);
 
            // else insert into decreasing sequence set
            else
                s2.insert(x[i]);
        }
 
        // finding the length
        int ans = s1.size() + s2.size();
        cout << ans << "\n";
    }
 
    // printing the sequence
    set<int>::iterator it;
    for (it = s1.begin(); it != s1.end(); it++)
        cout << (*it) << " ";
 
    set<int>::reverse_iterator rit;
 
    for (rit = s2.rbegin(); rit != s2.rend(); rit++)
        cout << (*rit) << " ";
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 5, 2 };
    int n = sizeof(a) / sizeof(a[0]);
    int x[] = { 5, 1, 3, 2 };
    int q = sizeof(x) / sizeof(x[0]);
 
    solveQuery(a, n, x, q);
    return 0;
}

// Java implementation of above approach
import java.util.*;
 
class GFG
{
 
// Function to find the bitonic sequence
static void solveQuery(int a[], int n, int x[], int q)
{
    int maxx = Integer.MIN_VALUE;
 
    // Finding the maximum element
    for (int i = 0; i < n; i++)
        maxx = Math.max(maxx, a[i]);
 
    Set<Integer> s1 = new HashSet<>(), s2 = new HashSet<>();
 
    s1.add(a[0]);
    s2.add(a[n - 1]);
 
    // set to include increasing sequence element
    for (int i = 1; i < n; i++)
        if (a[i] > a[i - 1])
            s1.add(a[i]);
 
    // set to include decreasing sequence element
    for (int i = n - 2; i >= 0; i--)
        if (a[i] > a[i + 1])
            s2.add(a[i]);
 
    // removing maximum element from
    // decreasing sequence set
    s2.remove(maxx);
 
    // for each query
    for (int i = 0; i < q; i++)
    {
 
        // checking if x is greater than
        // maximum element or not.
        if (maxx <= x[i])
        {
            maxx = x[i];
            s1.add(x[i]);
        }
 
        else
        {
 
            // checking if x lie in increasing sequence
            if (!s1.contains(x[i]))
                s1.add(x[i]);
 
            // else insert into decreasing sequence set
            else
                s2.add(x[i]);
        }
 
        // finding the length
        int ans = s1.size() + s2.size();
        System.out.print(ans + "\n");
    }
 
    // printing the sequence
    for (Integer it : s1)
        System.out.print((it) + " ");
 
    for (Integer it : s2)
        System.out.print((it) + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 2, 5, 2 };
    int n = a.length;
    int x[] = { 5, 1, 3, 2 };
    int q = x.length;
 
    solveQuery(a, n, x, q);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of above approach
import sys
 
# Function to find the bitonic sequence
def solveQuery(a, n, x, q):
    maxx = -sys.maxsize
 
    # Finding the maximum element
    for i in range(n):
        maxx = max(maxx, a[i])
 
    s1, s2 = set(), set()
 
    s1.add(a[0])
    s2.add(a[n - 1])
 
    # set to include increasing sequence element
    for i in range(1, n):
        if a[i] > a[i - 1]:
            s1.add(a[i])
 
    # set to include decreasing sequence element
    for i in range(n - 2, -1, -1):
        if a[i] > a[i + 1]:
            s2.add(a[i])
 
    # removing maximum element from
    # decreasing sequence set
    s2.remove(maxx)
 
    # for each query
    for i in range(q):
 
        # checking if x is greater than
        # maximum element or not.
        if maxx <= x[i]:
            maxx = x[i]
            s1.add(x[i])
        else:
 
            # checking if x lie in increasing sequence
            if x[i] not in s1:
                s1.add(x[i])
 
            # else insert into decreasing sequence set
            else:
                s2.add(x[i])
 
        # finding the length
        ans = len(s1) + len(s2)
        print(ans)
 
    # printing the sequence
    for i in s1:
        print(i, end = " ")
 
    for i in reversed(list(s2)):
        print(i, end = " ")
 
# Driver Code
if __name__ == "__main__":
 
    a = [1, 2, 5, 2]
    n = len(a)
    x = [5, 1, 3, 2]
    q = len(x)
 
    solveQuery(a, n, x, q)
 
# This code is contributed by
# sanjeev2552

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find the bitonic sequence
static void solveQuery(int []a, int n, int []x, int q)
{
    int maxx = int.MinValue;
 
    // Finding the maximum element
    for (int i = 0; i < n; i++)
        maxx = Math.Max(maxx, a[i]);
 
    HashSet<int> s1 = new HashSet<int>(), s2 = new HashSet<int>();
 
    s1.Add(a[0]);
    s2.Add(a[n - 1]);
 
    // set to include increasing sequence element
    for (int i = 1; i < n; i++)
        if (a[i] > a[i - 1])
            s1.Add(a[i]);
 
    // set to include decreasing sequence element
    for (int i = n - 2; i >= 0; i--)
        if (a[i] > a[i + 1])
            s2.Add(a[i]);
 
    // removing maximum element from
    // decreasing sequence set
    s2.Remove(maxx);
 
    // for each query
    for (int i = 0; i < q; i++)
    {
 
        // checking if x is greater than
        // maximum element or not.
        if (maxx <= x[i])
        {
            maxx = x[i];
            s1.Add(x[i]);
        }
 
        else
        {
 
            // checking if x lie in increasing sequence
            if (!s1.Contains(x[i]))
                s1.Add(x[i]);
 
            // else insert into decreasing sequence set
            else
                s2.Add(x[i]);
        }
 
        // finding the length
        int ans = s1.Count + s2.Count;
        Console.Write(ans + "\n");
    }
 
    // printing the sequence
    foreach (int it in s1)
        Console.Write((it) + " ");
 
    foreach (int it in s2)
        Console.Write((it) + " ");
}
 
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 2, 5, 2 };
    int n = a.Length;
    int []x = { 5, 1, 3, 2 };
    int q = x.Length;
 
    solveQuery(a, n, x, q);
}
}
 
// This code is contributed by Rajput-Ji

<script>
    // Javascript implementation of above approach
     
    // Function to find the bitonic sequence
    function solveQuery(a, n, x, q)
    {
        let maxx = Number.MIN_VALUE;
 
        // Finding the maximum element
        for (let i = 0; i < n; i++)
            maxx = Math.max(maxx, a[i]);
 
        let s1 = new Set();
        let s2 = new Set();
 
        s1.add(a[0]);
        s2.add(a[n - 1]);
 
        // set to include increasing sequence element
        for (let i = 1; i < n; i++)
            if (a[i] > a[i - 1])
                s1.add(a[i]);
 
        // set to include decreasing sequence element
        for (let i = n - 2; i >= 0; i--)
            if (a[i] > a[i + 1])
                s2.add(a[i]);
 
        // removing maximum element from
        // decreasing sequence set
        s2.delete(maxx);
 
        // for each query
        for (let i = 0; i < q; i++)
        {
 
            // checking if x is greater than
            // maximum element or not.
            if (maxx <= x[i])
            {
                maxx = x[i];
                s1.add(x[i]);
            }
 
            else
            {
 
                // checking if x lie in increasing sequence
                if (!s1.has(x[i]))
                    s1.add(x[i]);
 
                // else insert into decreasing sequence set
                else
                    s2.add(x[i]);
            }
 
            // finding the length
            let ans = s1.size + s2.size;
            document.write(ans + "</br>");
        }
         
        let S1 = Array.from(s1);
        S1.sort(function(a, b){return a - b});
 
        // printing the sequence
        S1.forEach (function(it) {
          document.write(it + " ");
        })
        s2.forEach (function(it) {
          document.write(it + " ");
        })
    }
     
    let a = [ 1, 2, 5, 2 ];
    let n = a.length;
    let x = [ 5, 1, 3, 2 ];
    let q = x.length;
   
    solveQuery(a, n, x, q);
 
// This code is contributed by decode2207.
</script>

4
5
6
6
1 2 3 5 2 1