Dada una array de tamaño N, inicialmente solo consta de ceros. La tarea es aplicar la operación dada q veces y encontrar la cantidad de números diferentes en la array, excepto los ceros.
Formato de operación: actualizar (l, r, x):: actualizar a[i] = x para todos (l <= i <= r).
Ejemplos:
Entrada: N = 5, Q = 3,
actualización (1, 3, 1)
actualización (0, 1, 2)
actualización (3, 3, 3)
Salida: 3
Explicación: inicialmente la array es {0, 0, 0, 0 , 0}. Después
de aplicar la operación por primera vez, la array se convierte en {0, 1, 1, 1, 0}.
Después de aplicar la operación por segunda vez, la array se convierte en
{2, 2, 1, 1, 0}. Después de aplicar la operación por tercera vez, la array
se convierte en {2, 2, 1, 3, 0}. Entonces, varios números diferentes esperan que el cero sea 3.Entrada: N = 5, Q = 3,
actualización (1, 1, 4)
actualización (0, 1, 2)
actualización (1, 4, 5)
Salida: 2
Enfoque:
cada operación sugiere una actualización de rango, por lo tanto, intente actualizar la array utilizando la propagación diferida . Después de aplicar la operación Q veces usando propagación perezosa, llame a una función que encuentre la cantidad de números diferentes en la array. Esta función usa un conjunto para encontrar el conteo de diferentes números.
Las operaciones de actualización y consulta son similares a las de un árbol de segmentos con algunos cambios. Cada vez que se ejecuta una consulta de actualización en un árbol de segmentos, todos los Nodes asociados con el Node actual también se actualizan, mientras que en la propagación diferida, esos Nodes solo se actualizarán cuando sea necesario, es decir, creamos una array perezosa[] de tamaño igual a la array dada . de cuyos elementos se inicializará a 0lo que significa que inicialmente no hay actualizaciones para ningún Node y cualquier valor distinto de cero en lazy[i] indica que el Node i tiene una actualización pendiente que solo se actualizará durante la consulta (cuando sea necesario).
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation for above approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// To store the tree in lazy propagation
int lazy[4 * N];
// To store the different numbers
set<int> se;
// Function to update in the range [x, y) with given value
void 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 code
int 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 approach
import java.util.*;
class geeks
{
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 approach
using System;
using System.Collections.Generic;
public class geeks
{
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 approach
var N = 100005;
// To store the tree in lazy propagation
var lazy = Array(4*N).fill(0);
// To store the different numbers
var se = new Set();
// Function to update in the range [x, y) with given value
function 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 queries
var 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
document.write(se.size);
</script>
3
Complejidad de tiempo: O (N * logN), ya que estamos usando dos llamadas recursivas y en cada llamada recursiva, estamos decrementando la división media por piso de 2.
Espacio auxiliar: O(N), ya que estamos usando el espacio extra implícito para la pila recursiva para las llamadas recursivas.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA