Encuentre el elemento Array después de consultas Q basadas en las condiciones dadas

Dada una array arr[] de longitud N y Q consultas de 3 tipos (1, 2, 3) cuyas operaciones son las siguientes:

• Tipo 1: la consulta tiene entrada como 1 y la tarea es invertir la array .
• Tipo 2: la consulta tiene entrada como (2 x) y la tarea de encontrar el índice de x en la array de resultados.
• Tipo 3: la consulta tiene entrada como (3 xy) y la tarea es intercambiar los elementos en el índice x e y en la array.

La tarea es imprimir el resultado de la consulta de tipo 2 .

Ejemplos:

Entrada: N = 5, arr[] = {3, 7, 8, 1, 33}, Q = 4, Consultas[][] = {{1}, {2, 8}, {3, 2, 4} , {2, 1}
Salida: 2 1
Explicación: la consulta del proceso primero es 1, así que invierta la lista [33, 1, 8, 7, 3], Segunda consulta 2 8, busque el índice del elemento 8 que es 2, tercera consulta es 3 2 4, así que intercambie el índice 2 y 4 con la nueva array = [33, 1, 3, 7, 8] ahora la última consulta es 2 1, así que encuentre el índice del elemento 1, que es 1, así que genere 2 1.

Entrada: N = 6, arr[] = {6, 33, 9, 22, 45, 4}, Q = 5, Consultas[][] = {{1}, {3, 0, 4}, {2, 33}, {1}, {2, 9}}
Salida: 0 2

Enfoque: el problema dado se puede resolver en función de las siguientes suposiciones para cada consulta:

• Use una bandera variable = 1 y para cada consulta de tipo 1 , multiplique la bandera * -1 para que, por negativo, indique una inversión de la lista y manipule el cálculo en orden inverso en lugar de invertir directamente la array y de esta manera reduce la complejidad del tiempo.
• Ahora, para la consulta de tipo 3 xy , use la estructura de datos del mapa para almacenar el índice y el elemento como pares de clave y valor e intercambie directamente los valores en O(1) .
• Finalmente, para la consulta de tipo 2 x, obtenga directamente el índice.

Siga los pasos a continuación para resolver el problema:

• Inicialice un mapa mp = {} para almacenar el elemento y su índice en la array como par clave-valor .
• Inicialice el indicador de variable como 1 para llevar la cuenta del número de veces que se invierte la array.
• Itere sobre el rango [0, Q) usando la variable i y realice las siguientes tareas:
  • Primero, verifique el tipo de consulta mientras toma cada consulta como entrada.
  • Para la consulta de tipo 1 , en lugar de invertir manualmente, lo que aumentará la complejidad del tiempo, cambie el signo del indicador de variable para indicar que la array es normal o invertida.
  • Para la consulta de tipo 2 , encuentre el índice del valor dado del mapa y, si la array no está invertida, imprima el valor de m[x] como resultado. De lo contrario, imprima el valor de (N – m[x] – 1) .
  • Para la consulta de tipo 3 , primero, encuentre los valores en el índice dado y luego intercambie el valor y el índice en la lista y el mapa respectivamente.

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

// C++ program for the above approach
 
// Function to perform the given queries
// and print the result accordingly
#include<bits/stdc++.h>
using namespace std;
 
void arrayManipulation(int n,vector<int> arr,int q,vector<vector<int>> qarr){
 
    // Stores the index value pair
    unordered_map<int,int>mp;
    vector<int>ans;
 
    // Flag to indicate reversal
    int flg = 1;
    for(int i=0;i<n;i++){
        mp[arr[i]] = i;
    }
 
    // Processing each query
    for(int i=0;i<q;i++){
        vector<int>a = qarr[i];
 
        // Type 1 flag multiplied -1
        if(a[0] == 1)
            flg *= -1;
             
        // Type 2 query taking index
        // value acc. to flag sign
        else if(a[0] == 2){
            int x = a[1];
            if(flg == -1)
                ans.push_back(n-mp[x]-1);
            else
                ans.push_back(mp[x]);
        }
                 
        // Type 3 query swaping value
        // directly in map
        else{
            int x = a[1];
            int y = a[2];
 
            // Stores the value to swap
            // and update the array
            int x1 = a[1];
            int y1 = a[2];
            if(flg == -1){
                y = n-y-1;
                x = n-x-1;
            }
 
            // Value swapped and store
            // value to swap and update
            // the map
            y = arr[y];
            x = arr[x];
 
            // Index swapped
            swap(arr[x1],arr[y1]);
            swap(mp[x],mp[y]);
        }
    }
 
    // Print the result for queries
    for(auto x:ans){
        cout<<x<<" ";
    }
 
}
 
// Driver Code
int main(){
 
int N = 6;
vector<int> arr = {6, 33, 9, 22, 45, 4};
int Q = 5;
vector<vector<int>>Queries = {{1}, {3, 0, 4}, {2, 33}, {1}, {2, 9}};
   
// Function Call
arrayManipulation(N, arr, Q, Queries);
 
}
 
// This code is contributed by shinjanpatra

# Python program for the above approach
 
# Function to perform the given queries
# and print the result accordingly
def arrayManipulation(n, arr, q, qarr):
 
    # Stores the index value pair
    mp = {}
    ans = []
 
    # Flag to indicate reversal
    flg = 1
    for i in range(n):
        mp[arr[i]] = i
 
    # Processing each query
    for i in range(q):
        a = qarr[i]
 
        # Type 1 flag multiplied -1
        if(a[0] == 1):
            flg *= -1
             
        # Type 2 query taking index
        # value acc. to flag sign
        elif(a[0] == 2):
            x = a[1]
            if(flg == -1):
                ans.append(n-mp[x]-1)
            else:
                ans.append(mp[x])
                 
        # Type 3 query swaping value
        # directly in map
        else:
            x = a[1]
            y = a[2]
 
            # Stores the value to swap
            # and update the array
            x1 = a[1]
            y1 = a[2]
            if(flg == -1):
                y = n-y-1
                x = n-x-1
 
            # Value swapped and store
            # value to swap and update
            # the map
            y = arr[y]
            x = arr[x]
 
            # Index swapped
            arr[x1], arr[y1] = arr[y1], arr[x1]
            mp[x], mp[y] = mp[y], mp[x]
 
    # Print the result for queries
    print(*ans)
 
 
# Driver Code
N = 6
arr = [6, 33, 9, 22, 45, 4]
Q = 5
Queries = [[1], [3, 0, 4], [2, 33], [1], [2, 9]]
 
# Function Call
arrayManipulation(N, arr, Q, Queries)

0 2

Complejidad de tiempo: O(max(N, Q))
Espacio auxiliar: O(N)