Given an array of size N, initially consists of zeroes only. The task is to apply the given operation q times and find the number of different numbers in the array except for zeroes.
Operation Format: update(l, r, x):: update a[i] = x for all (l <= i <= r).
Examples:
Input : N = 5, Q = 3,
update(1, 3, 1)
update(0, 1, 2)
update(3, 3, 3)
Output : 3
Explanation : Initially array is {0, 0, 0, 0, 0}. After
applying the operation for the first time array becomes {0, 1, 1, 1, 0}.
After applying the operation for the second time the array becomes
{2, 2, 1, 1, 0}. After applying the operation for the third time the array
becomes {2, 2, 1, 3, 0}. So, a number of different numbers expect zero are 3.Input : N = 5, Q = 3,
update(1, 1, 4)
update(0, 1, 2)
update(1, 4, 5)
Output : 2
Approach :
Each operation suggests a range update, hence try to update the array using lazy propagation. After applying the operation Q times using lazy propagation call a function that finds the number of different numbers in the array. This function uses a set to find the count of different numbers.
The update and query operations are similar to what they are in a segment tree with some changes. Whenever an update query gets executed in a segment tree, all the nodes associated with the current node also get updated whereas in lazy propagation those nodes will only get updated when required i.e. we create an array lazy[] of size equal to the given array all of whose elements will be initialized to 0 which means there are no updates for any node initially and any non-zero value at lazy[i] indicates that node i has an update pending which will only be updated while querying (when required).
Below is the implementation of the above approach :
C++
// CPP implementation for above approach#include <bits/stdc++.h>using namespace std;#define N 100005// To store the tree in lazy propagationint lazy[4 * N];// To store the different numbersset<int> se;// Function to update in the range [x, y) with given valuevoid update(int x, int y, int value, int id, int l, int r){ // check out of bound if (x >= r or l >= y) return; // check for complete overlap if (x <= l && r <= y) { lazy[id] = value; return; } // find the mid number int mid = (l + r) / 2; // check for pending updates if (lazy[id]) lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; // make lazy[id] = 0, so that it has no pending updates lazy[id] = 0; // call for two child nodes update(x, y, value, 2 * id, l, mid); update(x, y, value, 2 * id + 1, mid, r);}// Function to find non-zero integers in the range [l, r)void query(int id, int l, int r){ // if id contains positive number if (lazy[id]) { se.insert(lazy[id]); // There is no need to see the children, // because all the interval have same number return; } // check for out of bound if (r - l < 2) return; // find the middle number int mid = (l + r) / 2; // call for two child nodes query(2 * id, l, mid); query(2 * id + 1, mid, r);}// Driver codeint main(){ // size of the array and number of queries int n = 5, q = 3; // Update operation for l, r, x, id, 0, n update(1, 4, 1, 1, 0, n); update(0, 2, 2, 1, 0, n); update(3, 4, 3, 1, 0, n); // Query operation to get answer in the range [0, n-1] query(1, 0, n); // Print the count of non-zero elements cout << se.size() << endl; return 0;} |
Java
// Java implementation for above approachimport java.util.*;class neveropen{ static int N = 100005; // To store the tree in lazy propagation static int[] lazy = new int[4*N]; // To store the different numbers static Set<Integer> se = new HashSet<Integer>(); // Function to update in the range [x, y) with given value public static void update(int x, int y, int value, int id, int l, int r) { // check out of bound if (x >= r || l >= y) return; // check for complete overlap if (x <= l && r <= y) { lazy[id] = value; return; } // find the mid number int mid = (l + r) / 2; // check for pending updates if (lazy[id] != 0) lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; // make lazy[id] = 0, so that it has no pending updates lazy[id] = 0; // call for two child nodes update(x, y, value, 2 * id, l, mid); update(x, y, value, 2 * id + 1, mid, r); } // Function to find non-zero integers in the range [l, r) public static void query(int id, int l, int r) { // if id contains positive number if (lazy[id] != 0) { se.add(lazy[id]); // There is no need to see the children, // because all the interval have same number return; } // check for out of bound if (r - l < 2) return; // find the middle number int mid = (l + r) / 2; // call for two child nodes query(2 * id, l, mid); query(2 * id + 1, mid, r); } // Driver Code public static void main(String[] args) { // size of the array and number of queries int n = 5, q = 3; // Update operation for l, r, x, id, 0, n update(1, 4, 1, 1, 0, n); update(0, 2, 2, 1, 0, n); update(3, 4, 3, 1, 0, n); // Query operation to get answer in the range [0, n-1] query(1, 0, n); // Print the count of non-zero elements System.out.println(se.size()); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 implementation for above approach N = 100005# To store the tree in lazy propagation lazy = [0] * (4 * N); # To store the different numbers se = set() # Function to update in the range [x, y)# with given value def update(x, y, value, id, l, r) : # check out of bound if (x >= r or l >= y): return; # check for complete overlap if (x <= l and r <= y) : lazy[id] = value; return; # find the mid number mid = (l + r) // 2; # check for pending updates if (lazy[id]) : lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; # make lazy[id] = 0, # so that it has no pending updates lazy[id] = 0; # call for two child nodes update(x, y, value, 2 * id, l, mid); update(x, y, value, 2 * id + 1, mid, r); # Function to find non-zero integers# in the range [l, r) def query(id, l, r) : # if id contains positive number if (lazy[id]) : se.add(lazy[id]); # There is no need to see the children, # because all the interval have same number return; # check for out of bound if (r - l < 2) : return; # find the middle number mid = (l + r) // 2; # call for two child nodes query(2 * id, l, mid); query(2 * id + 1, mid, r); # Driver code if __name__ == "__main__" : # size of the array and number of queries n = 5; q = 3; # Update operation for l, r, x, id, 0, n update(1, 4, 1, 1, 0, n); update(0, 2, 2, 1, 0, n); update(3, 4, 3, 1, 0, n); # Query operation to get answer # in the range [0, n-1] query(1, 0, n); # Print the count of non-zero elements print(len(se)); # This code is contributed by AnkitRai01 |
C#
// C# implementation for above approachusing System;using System.Collections.Generic; public class neveropen{ static int N = 100005; // To store the tree in lazy propagation static int[] lazy = new int[4*N]; // To store the different numbers static HashSet<int> se = new HashSet<int>(); // Function to update in the range [x, y) with given value public static void update(int x, int y, int value, int id, int l, int r) { // check out of bound if (x >= r || l >= y) return; // check for complete overlap if (x <= l && r <= y) { lazy[id] = value; return; } // find the mid number int mid = (l + r) / 2; // check for pending updates if (lazy[id] != 0) lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; // make lazy[id] = 0, so that it has no pending updates lazy[id] = 0; // call for two child nodes update(x, y, value, 2 * id, l, mid); update(x, y, value, 2 * id + 1, mid, r); } // Function to find non-zero integers in the range [l, r) public static void query(int id, int l, int r) { // if id contains positive number if (lazy[id] != 0) { se.Add(lazy[id]); // There is no need to see the children, // because all the interval have same number return; } // check for out of bound if (r - l < 2) return; // find the middle number int mid = (l + r) / 2; // call for two child nodes query(2 * id, l, mid); query(2 * id + 1, mid, r); } // Driver Code public static void Main(String[] args) { // size of the array and number of queries int n = 5, q = 3; // Update operation for l, r, x, id, 0, n update(1, 4, 1, 1, 0, n); update(0, 2, 2, 1, 0, n); update(3, 4, 3, 1, 0, n); // Query operation to get answer in the range [0, n-1] query(1, 0, n); // Print the count of non-zero elements Console.WriteLine(se.Count); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation for above approachvar N = 100005;// To store the tree in lazy propagationvar lazy = Array(4*N).fill(0);// To store the different numbersvar se = new Set();// Function to update in the range [x, y) with given valuefunction update(x, y, value, id, l, r){ // check out of bound if (x >= r || l >= y) return; // check for complete overlap if (x <= l && r <= y) { lazy[id] = value; return; } // find the mid number var mid = parseInt((l + r) / 2); // check for pending updates if (lazy[id] != 0) lazy[2 * id] = lazy[2 * id + 1] = lazy[id]; // make lazy[id] = 0, so that it has no pending updates lazy[id] = 0; // call for two child nodes update(x, y, value, 2 * id, l, mid); update(x, y, value, 2 * id + 1, mid, r); }// Function to find non-zero integers in the range [l, r)function query(id, l, r){ // if id contains positive number if (lazy[id] != 0) { se.add(lazy[id]); // There is no need to see the children, // because all the interval have same number return; } // check for out of bound if (r - l < 2) return; // find the middle number var mid = parseInt((l + r) / 2); // call for two child nodes query(2 * id, l, mid); query(2 * id + 1, mid, r);}// Driver Code// size of the array and number of queriesvar n = 5, q = 3;// Update operation for l, r, x, id, 0, nupdate(1, 4, 1, 1, 0, n);update(0, 2, 2, 1, 0, n);update(3, 4, 3, 1, 0, n);// Query operation to get answer in the range [0, n-1]query(1, 0, n);// Print the count of non-zero elementsdocument.write(se.size);</script> |
Output:
3
Time Complexity: O(N*logN), as we are using two recursive calls and in each recursive call, we are decrementing mid by floor division of 2.
Auxiliary Space: O(N), as we are using the implicit extra space for the recursive stack for the recursive calls.
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!
