Dada una array , arr[] de tamaño N , un entero P y una array 2D Q[][] que consta de consultas del siguiente tipo:
- 1 LRB[R – L + 1]: La tarea de esta consulta es reemplazar el subarreglo {arr[L], … arr[R] con el arreglo B[] b dado que cualquier elemento del arreglo se puede reemplazar como máximo P veces .
- 2 X: la tarea de esta consulta es imprimir arr[X] .
Ejemplos:
Entrada: arr[] = {3, 10, 4, 2, 8, 7}, P = 1, Q[][] = {{1, 0, 3, 3, 2, 1, 11}, {2, 3}, {1, 2, 3, 5, 7}, {2, 2} }
Salida : 11 1
Explicación:
Consulta 1: Reemplazar el subarreglo {arr[0], …, arr[3]} con el arreglo { 3, 2, 1, 11} modifica arr[] a {3, 2, 1, 11, 8, 7}
Consulta 2: Imprimir arr[3].
Consulta 3: dado que P = 1, el subarreglo {arr[2], …, arr[3]} no se puede reemplazar más de una vez.
Consulta 4: Imprimir arr[2].Entrada: arr[] = {1, 2, 3, 4, 5}, P = 2, Q[][] = {{2, 0}, {1, 1, 3, 6, 7, 8}, { 1, 3, 4, 10, 12}, {2, 4}}
Salida: 1 12
Enfoque: El problema se puede resolver utilizando el algoritmo Union-Find . La idea es recorrer el arreglo Q[][] y verificar si Q[0] es igual a 1 o no. Si se determina que es cierto, reemplace el subarreglo con el nuevo arreglo y cada vez que cualquier elemento del arreglo haya sido reemplazado P veces, luego cree un nuevo subconjunto usando union-find . Siga los pasos a continuación para resolver el problema:
- Inicialice una array, digamos visitado [] , donde visitado [i] el índice de verificación i está presente en cualquier subconjunto disjunto o no.
- Inicialice una array, digamos count[] , donde count[i] almacena cuántas veces se ha reemplazado arr[i] .
- Inicialice una array, digamos last[] , para almacenar el elemento más grande de cada subconjunto disjunto.
- Inicialice una array, digamos parent[] , para almacenar el elemento más pequeño de cada subconjunto disjunto.
- Recorra la array Q[][] y para cada consulta verifique si Q[i][0] == 1 o no. Si se encuentra que es cierto, realice las siguientes operaciones:
- Itere sobre el rango [Q[i][1], Q[i][2]] usando la variable low y verifique si visited[low] es verdadero o no. Si se determina que es cierto, busque el padre de ese subconjunto donde está presente Low , busque el elemento más grande presente en el subconjunto.
- De lo contrario, verifique si count[low] es menor que P o no. Si se determina que es cierto, reemplace el valor de arr[bajo] con el valor correspondiente.
- De lo contrario, verifique si count[low] es igual a P o no. Si se determina que es cierto, cree un nuevo subconjunto separado del índice actual.
- De lo contrario, imprima arr[Q[i][1]]] .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// visited[i]: Check index i is present
// in any disjoint subset or not.
static boolean[] visited;
// Store the smallest element
// of each disjoint subset
static int[] parent;
// count[i]: Stores the count
// of replacements of arr[i]
static int[] last;
// Store the largest element
// of each disjoint subset
static int[] count;
// Function to process all the given Queries
static void processQueries(int[] arr, int P,
List<List<Integer> > Q)
{
// Traverse the queries[][] array
for (int i = 0; i < Q.size(); i++) {
// Stores the current query
List<Integer> query = Q.get(i);
// If query of type is 1
if (query.get(0) == 1) {
// Perform the query of type 1
processTypeOneQuery(query, arr, P);
}
// If query of type is 2
else {
// Stores 2nd element of
// current query
int index = query.get(1);
// Print arr[index]
System.out.println(arr[index]);
}
}
}
// Function to perform the query of type 1
static void processTypeOneQuery(
List<Integer> query, int[] arr, int P)
{
// Stores the value of L
int low = query.get(1);
// Stores the value of R
int high = query.get(2);
// Stores leftmost index of the
// subarray for which a new
// subset can be generated
int left = -1;
// Stores index of
// the query[] array
int j = 3;
// Iterate over the
// range [low, high]
while (low <= high) {
// If low is present in
// any of the subset
if (visited[low]) {
// If no subset created for
// the subarray arr[left...low - 1]
if (left != -1) {
// Create a new subset
newUnion(left, low - 1,
arr.length);
// Update left
left = -1;
}
// Stores next index to be
// processed
int jump = findJumpLength(low);
// Update low
low += jump;
// Update j
j += jump;
}
// If arr[low] has been
// already replaced P times
else if (count[low] == P) {
// If already subset
// created for left
if (left == -1) {
// Update left
left = low;
}
// Mark low as an element
// of any subset
visited[low] = true;
// Update low
low++;
// Update j
j++;
}
// If arr[low] has been replaced
// less than P times
else {
// If no subset created for
// the subarray arr[left...low - 1]
if (left != -1) {
// Create a new subset
newUnion(left, low - 1, arr.length);
// Update left
left = -1;
}
// Replace arr[low] with
// the corresponding value
arr[low] = query.get(j);
// Update count[low]
count[low]++;
// Update low
low++;
// Update j
j++;
}
}
// If no subset has been created for
// the subarray arr[left...low - 1]
if (left != -1) {
// Create a new subset
newUnion(left, high, arr.length);
}
}
// Function to find the next index
// to be processed after visiting low
static int findJumpLength(int low)
{
// Stores smallest index of
// the subset where low present
int p = findParent(low);
// Stores next index
// to be processed
int nextIndex = last[p] + 1;
// Stores difference between
// low and nextIndex
int jump = (nextIndex - low);
// Return jump
return jump;
}
// Function to create a new subset
static void newUnion(int low, int high,
int N)
{
// Iterate over
// the range [low + 1, high]
for (int i = low + 1; i <= high;
i++) {
// Perform union operation
// on low
union(low, i);
}
// If just smaller element of low
// is present in any of the subset
if (low > 0 && visited[low - 1]) {
// Perform union on (low - 1)
union(low - 1, low);
}
// If just greater element of high
// is present in any of the subset
if (high < N - 1 && visited[high + 1]) {
// Perform union on high
union(high, high + 1);
}
}
// Function to find the smallest
// element of the subset
static int findParent(int u)
{
// Base Case
if (parent[u] == u)
return u;
// Stores smallest element
// of parent[u
return parent[u]
= findParent(parent[u]);
}
// Function to perform union operation
static void union(int u, int v)
{
// Stores smallest element
// of subset containing u
int p1 = findParent(u);
// Stores smallest element
// of subset containing u
int p2 = findParent(v);
// Update parent[p2]
parent[p2] = p1;
// Update last[p1]
last[p1] = last[p2];
}
// Function to find all the queries
static List<List<Integer> > getQueries()
{
// Stores all the queries
List<List<Integer> > Q
= new ArrayList<List<Integer> >();
// Initialize all queries
Integer[] query1 = { 1, 0, 3, 3, 2,
1, 11 };
Integer[] query2 = { 2, 3 };
Integer[] query3 = { 1, 2, 3, 5, 7 };
Integer[] query4 = { 2, 2 };
// Insert all queries
Q.add(Arrays.asList(query1));
Q.add(Arrays.asList(query2));
Q.add(Arrays.asList(query3));
Q.add(Arrays.asList(query4));
// Return all queries
return Q;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 3, 10, 4, 2, 8, 7 };
int N = arr.length;
int P = 1;
parent = new int[N];
last = new int[N];
count = new int[N];
visited = new boolean[N];
// Initialize parent[] and
// last[] array
for (int i = 0; i < parent.length;
i++) {
// Update parent[i]
parent[i] = i;
// Update last[i]
last[i] = i;
}
List<List<Integer> > Q = getQueries();
processQueries(arr, P, Q);
}
}
Python3
# Python3 program to implement # the above approach # visited[i]: Check index i is present # in any disjoint subset or not. visited = [] # Store the smallest element # of each disjoint subset parent = [] # count[i]: Stores the count # of replacements of arr[i] last = [] # Store the largest element # of each disjoint subset count = [] # Function to process all the given Queries def processQueries(arr, P, Q): # Traverse the [,]queries array for i in range(len(Q)): # Stores the current query query = Q[i]; # If query of type is 1 if (query[0] == 1): # Perform the query of type 1 processTypeOneQuery(query, arr, P); # If query of type is 2 else: # Stores 2nd element of # current query index = query[1]; # Print arr[index] print(arr[index]); # Function to perform the query of type 1 def processTypeOneQuery(query, arr, P): # Stores the value of L low = query[1]; # Stores the value of R high = query[2]; # Stores leftmost index of the # subarray for which a new # subset can be generated left = -1; # Stores index of # the query[] array j = 3; # Iterate over the # range [low, high] while (low <= high): # If low is present in # any of the subset if (visited[low]): # If no subset created for # the subarray arr[left...low - 1] if (left != -1): # Create a new subset newUnion(left, low - 1,len(arr)); # Update left left = -1; # Stores next index to be # processed jump = findJumpLength(low); # Update low low += jump; # Update j j += jump; # If arr[low] has been # already replaced P times elif (count[low] == P): # If already subset # created for left if (left == -1): # Update left left = low; # Mark low as an element # of any subset visited[low] = True; # Update low low += 1 # Update j j += 1 # If arr[low] has been replaced # less than P times else: # If no subset created for # the subarray arr[left...low - 1] if (left != -1): # Create a new subset newUnion(left, low - 1, len(arr)); # Update left left = -1; # Replace arr[low] with # the corresponding value arr[low] = query[j]; # Update count[low] count[low] += 1 # Update low low += 1 # Update j j += 1 # If no subset has been created for # the subarray arr[left...low - 1] if (left != -1): # Create a new subset newUnion(left, high, len(arr)); # Function to find the next index # to be processed after visiting low def findJumpLength(low): # Stores smallest index of # the subset where low present p = findParent(low); # Stores next index # to be processed nextIndex = last[p] + 1; # Stores difference between # low and nextIndex jump = (nextIndex - low); # Return jump return jump; # Function to create a new subset def newUnion(low, high,N): # Iterate over # the range [low + 1, high] for i in range(low+1,high+1): # Perform union operation # on low union(low, i); # If just smaller element of low # is present in any of the subset if (low > 0 and visited[low - 1]): # Perform union on (low - 1) union(low - 1, low); # If just greater element of high # is present in any of the subset if (high < N - 1 and visited[high + 1]): # Perform union on high union(high, high + 1); # Function to find the smallest # element of the subset def findParent(u): # Base Case if (parent[u] == u): return u; # Stores smallest element # of parent[u parent[u]= findParent(parent[u]); return parent[u] # Function to perform union operation def union(u, v): # Stores smallest element # of subset containing u p1 = findParent(u); # Stores smallest element # of subset containing u p2 = findParent(v); # Update parent[p2] parent[p2] = p1; # Update last[p1] last[p1] = last[p2]; # Function to find all the queries def getQueries(): # Stores all the queries Q = [] # Initialize all queries query1 = [ 1, 0, 3, 3, 2,1, 11 ] query2 = [ 2, 3 ] query3 = [ 1, 2, 3, 5, 7 ] query4 = [ 2, 2 ] # Insert all queries Q.append(query1) Q.append(query2) Q.append(query3) Q.append(query4) # Return all queries return Q; # Driver Code if __name__=='__main__': arr = [ 3, 10, 4, 2, 8, 7 ] N = len(arr) P = 1; parent = [i for i in range(N)] last = [i for i in range(N)] count = [0 for i in range(N)] visited = [False for i in range(N)] Q = getQueries(); processQueries(arr, P, Q); # This code is contributed by rutvik_56.
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
public class GFG {
// visited[i]: Check index i is present
// in any disjoint subset or not.
static bool[] visited;
// Store the smallest element
// of each disjoint subset
static int[] parent;
// count[i]: Stores the count
// of replacements of arr[i]
static int[] last;
// Store the largest element
// of each disjoint subset
static int[] count;
// Function to process all the given Queries
static void processQueries(int[] arr, int P,
List<List<int> > Q)
{
// Traverse the [,]queries array
for (int i = 0; i < Q.Count; i++) {
// Stores the current query
List<int> query = Q[i];
// If query of type is 1
if (query[0] == 1) {
// Perform the query of type 1
processTypeOneQuery(query, arr, P);
}
// If query of type is 2
else {
// Stores 2nd element of
// current query
int index = query[1];
// Print arr[index]
Console.WriteLine(arr[index]);
}
}
}
// Function to perform the query of type 1
static void processTypeOneQuery(
List<int> query, int[] arr, int P)
{
// Stores the value of L
int low = query[1];
// Stores the value of R
int high = query[2];
// Stores leftmost index of the
// subarray for which a new
// subset can be generated
int left = -1;
// Stores index of
// the query[] array
int j = 3;
// Iterate over the
// range [low, high]
while (low <= high) {
// If low is present in
// any of the subset
if (visited[low]) {
// If no subset created for
// the subarray arr[left...low - 1]
if (left != -1) {
// Create a new subset
newUnion(left, low - 1,
arr.Length);
// Update left
left = -1;
}
// Stores next index to be
// processed
int jump = findJumpLength(low);
// Update low
low += jump;
// Update j
j += jump;
}
// If arr[low] has been
// already replaced P times
else if (count[low] == P) {
// If already subset
// created for left
if (left == -1) {
// Update left
left = low;
}
// Mark low as an element
// of any subset
visited[low] = true;
// Update low
low++;
// Update j
j++;
}
// If arr[low] has been replaced
// less than P times
else {
// If no subset created for
// the subarray arr[left...low - 1]
if (left != -1) {
// Create a new subset
newUnion(left, low - 1, arr.Length);
// Update left
left = -1;
}
// Replace arr[low] with
// the corresponding value
arr[low] = query[j];
// Update count[low]
count[low]++;
// Update low
low++;
// Update j
j++;
}
}
// If no subset has been created for
// the subarray arr[left...low - 1]
if (left != -1) {
// Create a new subset
newUnion(left, high, arr.Length);
}
}
// Function to find the next index
// to be processed after visiting low
static int findJumpLength(int low)
{
// Stores smallest index of
// the subset where low present
int p = findParent(low);
// Stores next index
// to be processed
int nextIndex = last[p] + 1;
// Stores difference between
// low and nextIndex
int jump = (nextIndex - low);
// Return jump
return jump;
}
// Function to create a new subset
static void newUnion(int low, int high,
int N)
{
// Iterate over
// the range [low + 1, high]
for (int i = low + 1; i <= high;
i++) {
// Perform union operation
// on low
union(low, i);
}
// If just smaller element of low
// is present in any of the subset
if (low > 0 && visited[low - 1]) {
// Perform union on (low - 1)
union(low - 1, low);
}
// If just greater element of high
// is present in any of the subset
if (high < N - 1 && visited[high + 1]) {
// Perform union on high
union(high, high + 1);
}
}
// Function to find the smallest
// element of the subset
static int findParent(int u)
{
// Base Case
if (parent[u] == u)
return u;
// Stores smallest element
// of parent[u
return parent[u]
= findParent(parent[u]);
}
// Function to perform union operation
static void union(int u, int v)
{
// Stores smallest element
// of subset containing u
int p1 = findParent(u);
// Stores smallest element
// of subset containing u
int p2 = findParent(v);
// Update parent[p2]
parent[p2] = p1;
// Update last[p1]
last[p1] = last[p2];
}
// Function to find all the queries
static List<List<int> > getQueries()
{
// Stores all the queries
List<List<int> > Q
= new List<List<int> >();
// Initialize all queries
int[] query1 = { 1, 0, 3, 3, 2,
1, 11 };
int[] query2 = { 2, 3 };
int[] query3 = { 1, 2, 3, 5, 7 };
int[] query4 = { 2, 2 };
// Insert all queries
Q.Add(new List<int>(query1));
Q.Add(new List<int>(query2));
Q.Add(new List<int>(query3));
Q.Add(new List<int>(query4));
// Return all queries
return Q;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 3, 10, 4, 2, 8, 7 };
int N = arr.Length;
int P = 1;
parent = new int[N];
last = new int[N];
count = new int[N];
visited = new bool[N];
// Initialize parent[] and
// last[] array
for (int i = 0; i < parent.Length;
i++) {
// Update parent[i]
parent[i] = i;
// Update last[i]
last[i] = i;
}
List<List<int> > Q = getQueries();
processQueries(arr, P, Q);
}
}
// This code is contributed by Amit Katiyar
Producción:
11 1
Complejidad temporal: O(N + |Q| * P)
Espacio auxiliar: O(N)