Given an array, arr[] of size N, an integer P and a 2D array Q[][] consisting of queries of the following type:
- 1 L R B[R – L + 1]: The task for this query is to replace the subarray {arr[L], … arr[R] with the array B[] b given that any array element can be replaced at most P times.
- 2 X: The task for this query is to print arr[X].
Examples:
Input: 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} }
Output: 11 1
Explanation:
Query 1: Replacing the subarray {arr[0], …, arr[3]} with the array {3, 2, 1, 11} modifies arr[] to {3, 2, 1, 11, 8, 7}
Query 2: Print arr[3].
Query 3: Since P = 1, therefore the subarray {arr[2], …, arr[3]} can’t be replaced more than once.
Query 4: Print arr[2].Input: arr[] = {1, 2, 3, 4, 5}, P = 2, Q[][] = {{2, 0}, {1, 1, 3, 6, 7, 8}, {1, 3, 4, 10, 12}, {2, 4}}
Output: 1 12
Approach: The problem can be solved using the Union-Find algorithm. The idea is to traverse the array Q[][] and check if Q[0] is equal to 1 or not. If found to be true, then replace the subarray with the new array and whenever any array element has been replaced P times, then create a new subset using the union-find. Follow the steps below to solve the problem:
- Initialize an array, say visited[], where visited[i] check index i is present in any disjoint subset or not.
- Initialize an array, say count[], where count[i] stores how many times arr[i] has been replaced.
- Initialize an array, say last[], to store the largest element of each disjoint subset.
- Initialize an array, say parent[], to store the smallest element of each disjoint subset.
- Traverse the Q[][] array and for each query check if Q[i][0] == 1 or not. If found to be true then perform the following operations:
- Iterate over the range [ Q[i][1], Q[i][2] ] using variable low and check if visited[low] is true or not. If found to be true then find the parent of that subset where low present, find the largest element present in the subset.
- Otherwise, check if count[low] is less than P or not. If found to be true then replace the value of arr[low] with the corresponding value.
- Otherwise, check if count[low] is equal to P or not. If found to be true then create a new disjoint subset of the current index.
- Otherwise, print arr[Q[i][1]]].
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// visited[i]: Check index i is present// in any disjoint subset or not.bool visited[100001];// Store the smallest element// of each disjoint subsetint parent[100001];// count[i]: Stores the count// of replacements of arr[i]int last[100001];// Store the largest element// of each disjoint subsetint Count[100001];// Function to find the smallest// element of the subsetint findParent(int i) { // Base Case if (parent[i] == i) { return i; } // Stores smallest element // of parent[u] return parent[i] = findParent(parent[i]);}// Function to perform union operationvoid Union(int u, int v, int arr[]) { // Stores smallest element // of subset containing u int p1=findParent(u); // Stores smallest element // of subset containing v int p2=findParent(v); // Update parent[p2] parent[p2] = p1; // Update last[p1] last[p1] = last[p2];}// Function to create a new subsetvoid newUnion(int low, int high, int arr[]) { // Iterate over // the range [low + 1, high] for (int i = low + 1; i <= high; i++) { // Perform union operation // on low Union(low, i, arr); } // 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, arr); } // If just greater element of high // is present in any of the subset int N = sizeof(arr) / sizeof(arr[0]); if (high < N - 1 && visited[high + 1]) { // Perform union on high Union(high, high + 1,arr); }}// Function to find the next index// to be processed after visiting lowint 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 perform the query of type 1void processTypeOneQuery(vector<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 Union(low - 1, left, arr); // 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 Union(low - 1, left, arr); // 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); }}// Function to process all the given Queriesvoid processQueries(int arr[], int P, vector<vector<int>> Q) { // Traverse the queries[][] array for (int i = 0; i < Q.size(); i++) { // Stores the current query vector<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] cout << arr[index] << endl; } }}// Function to find all the queriesstatic vector<vector<int>> getQueries(){ // Stores all the queries vector<vector<int>> Q; // Initialize all queries array<int, 7> query1 = { 1, 0, 3, 3, 2, 1, 11 }; array<int, 2> query2 = { 2, 3 }; array<int, 5> query3 = { 1, 2, 3, 5, 7 }; array<int, 2> query4 = { 2, 2 }; // Insert all queries Q.push_back(vector<int>(query1.begin(), query1.end())); Q.push_back(vector<int>(query2.begin(), query2.end())); Q.push_back(vector<int>(query3.begin(), query3.end())); Q.push_back(vector<int>(query4.begin(), query4.end())); // Return all queries return Q;} // Driver Codeint main() { int arr[] = { 3, 10, 4, 2, 8, 7 }; int N = sizeof(arr) / sizeof(arr[0]); int P=1; vector<vector<int>> Q; // Initialize parent[] and // last[] array for (int i = 0; i < N; i++) { // Update parent[i] parent[i] = i; // Update last[i] last[i] = i; } Q=getQueries(); processQueries(arr, P, Q);}// This code is contributed by Utkarsh |
Java
// Java program to implement// the above approachimport 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 subsetparent = []# count[i]: Stores the count# of replacements of arr[i]last = []# Store the largest element# of each disjoint subsetcount = []# Function to process all the given Queriesdef 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 1def 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 lowdef 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 subsetdef 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 subsetdef 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 operationdef 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 queriesdef 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 Codeif __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 approachusing 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 |
Output:
11 1
Time Complexity: O(N + |Q| * P)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
