Dada una array que consta de N enteros positivos y Q consultas donde cada consulta es uno de los siguientes tipos:
- 1 lr : requiere imprimir el recuento de primoriales en el rango de índices [l, r] .
- 2 px : necesita asignar un valor x en un índice p dado .
Ejemplos:
Entrada: arr[] = {25, 2, 7, 30, 1} consultas = { {1, 1, 4 }, {2, 2, 6}, {1, 0, 3} }
Salida: 2 3
Explicación: En la primera consulta, busque primoriales del índice [1, 4].
Entonces, para índices en el rango [1, 4] solo 2 y 30. Estos dos elementos son primoriales porque 2
es el primer número primo y 30 = 2*3*5 (producto de los primeros tres números primos).
Entonces, la salida es 2 para esta consulta.
En la segunda consulta, asigne un valor = 6 en el índice 2. Ahora la array se verá así: { 25, 2, 6, 30, 1}.
En la tercera consulta, hay 3 números enteros que son primoriales en el rango [0, 3], es decir, {2, 6, 30}. Entonces la salida es 3.Entrada: arr[] = {210, 2, 6, 30, 2310}, queries = { {1, 2, 4}, {1, 0, 4}}
Salida: 3 5
Explicación: Todos los elementos de la array anterior son primordial.
210 = 2*3*5*7
2310 = 2*3*5*7*11
Enfoque ingenuo: el enfoque básico es almacenar números primos en orden ascendente utilizando el método tamiz . Luego, para cada consulta del primer tipo, verifique todos los elementos en ese rango y encuentre el recuento de primoriales y para el segundo tipo de consulta, asigne ese valor al índice dado.
Siga los pasos a continuación para saber si un número es primorial o no:
- Comience desde el primer número primo almacenado.
- Sigue multiplicando estos números primos almacenados.
- Si en cualquier punto el producto de números primos se vuelve igual a arr[i], entonces arr[i] es un primorial.
- Si el producto excede a arr[i], entonces arr[i] no es un primorial.
Siga la ilustración a continuación para tener una mejor comprensión de cómo encontrar un primorial
Ilustración:
Comprobar que arr[i]= 6 es primorial o no. inicialice cur con el primer número primo.
cur = 2;
cur = cur * 3, entonces ahora cur tiene valor 6 y arr[ i ] = 6. Entonces arr[ i ] es primorial.Para comprobar arr[i]= 10, es primorial o no. Inicialice cur con el primer primo 2.
cur = 2;
cur = cur * 3, entonces ahora cur tiene valor 6
cur = cur * 5 = 6 * 5 = 30.
Ahora cur tiene valor 30 y 30 es mayor que arr[i].
Entonces arr[i] = 10 no es un primorial.
Complejidad temporal: O(Q * N)
Espacio auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver de manera más eficiente al resolver las consultas en menos tiempo utilizando un árbol de segmentos basado en la siguiente observación:
Marque los primoriales presentes en la array y almacénelos en una estructura de datos de modo que podamos obtener el recuento de los primoriales dentro de un rango de índices y actualizar los valores cuando sea necesario en un tiempo óptimo.
Esta tarea se puede realizar mediante el uso de la estructura de datos del árbol de segmentos.
Siga el siguiente procedimiento para implementar la estructura de datos del árbol de segmentos.
- Guarde los primeros 15 primoriales en ( porque el 15º primorial está en orden de 10 17
- Marque los elementos de la array que son primoriales.
- En el árbol de segmentos, los Nodes hoja almacenan si el elemento correspondiente de la array es primorial o no (almacena 1 si es primorial; de lo contrario almacena 0) y los Nodes internos almacenan cuántos primoriales hay en ese rango dado (es decir, almacenan la suma de sus Nodes secundarios).
El siguiente es el árbol de segmentos para el ejemplo dado arr[ ] = {25, 2, 7, 30, 1} :
(cnt representa el conteo de primoriales correspondientes al rango cubierto por ese Node)
Para la consulta de tipo 2, si el valor asignado x es primorial, almacene 1 correspondiente a ese Node hoja; de lo contrario, almacene 0. Luego actualice los Nodes internos hasta la raíz del árbol de segmentos. Esto actualizará los recuentos de los rangos.
Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Usa la Tamiz de Eratóstenes para marcar todos los números primos.
- Almacene los valores primarios en un mapa (digamos primorial ) .
- Cree el árbol de segmentos para la array para el índice 0 a N-1.
- Ahora, para cada consulta del primer tipo, encuentre el valor de ese rango en el árbol de segmentos y para el segundo tipo actualice el árbol de segmentos con el valor dado .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to count primorials
// in the given range for Q queries
#include <bits/stdc++.h>
using namespace std;
const int mxx = 1e6 + 3;
vector<bool> isPrime(1000, true);
int segment[4 * mxx];
unordered_map<long long, int> primorial;
// Mark true all prime numbers
void sieve()
{
isPrime[0] = isPrime[1] = false;
for (int i = 2; i < 1000; i++) {
if (isPrime[i]) {
for (int j = 2 * i; j < 1000;
j = j + i)
// Mark false which are the
// multiple of prime numbers
isPrime[j] = false;
}
}
}
// Store primorials
void store_primorials()
{
int cnt = 0;
long long product = 1;
for (int i = 2; i < mxx && cnt < 15;
i++) {
if (isPrime[i]) {
product = product * 1LL * i;
primorial[product]++;
cnt++;
}
}
}
// To build segment tree
void build(int arr[], int low, int high,
int ind)
{
// The node is leaf node
if (low == high) {
// If array value is primorial
// assign leaf node value 1
// otherwise 0
auto it = primorial.find(arr[low]);
if (it != primorial.end())
segment[ind] = 1;
else
segment[ind] = 0;
return;
}
int mid = (low + high) >> 1;
// Go to the left and right child of
// current node
build(arr, low, mid, 2 * ind + 1);
build(arr, mid + 1, high, 2 * ind + 2);
// Calculate count of primorials for
// internal node of segment tree for
// corresponding ranges
segment[ind]
= segment[2 * ind + 1]
+ segment[2 * ind + 2];
}
// To update segment tree nodes
void update(int low, int high, int ind,
int pos, int val)
{
if (low == high) {
// If new assign value is primorial
// then mark it 1 otherwise 0
auto it = primorial.find(val);
if (it != primorial.end())
segment[ind] = 1;
else
segment[ind] = 0;
return;
}
int mid = (low + high) >> 1;
// Go to the left child if pos is on
// the left side of current node
if (pos >= low && pos <= mid)
update(low, mid, 2 * ind + 1,
pos, val);
// Go to the right child if pos is on
// the right side
else
update(mid + 1, high, 2 * ind + 2,
pos, val);
// Update all internal nodes of segment
// tree
segment[ind]
= segment[2 * ind + 1]
+ segment[2 * ind + 2];
}
// To compute answer for given range l to r
int range_queries(int l, int r, int low,
int high, int ind)
{
// [l, r] is given range, [low, high] is
// current range if current range is
// invalid return 0
if (high < l || low > r)
return 0;
// If current range is completely inside of
// the given range then return value of
// that node
if (low >= l && high <= r)
return segment[ind];
int mid = (low + high) >> 1;
// Go to the left child and right child
// to compute answer
return (
range_queries(l, r, low, mid,
2 * ind + 1)
+ range_queries(l, r, mid + 1, high,
2 * ind + 2));
}
// Function to find the count of primorials
vector<int> count(int arr[], int N,
vector<vector<int> >& queries)
{
vector<int> ans;
// Mark prime numbers as a true
sieve();
// To precompute primorials
store_primorials();
// Build segment tree for given array
build(arr, 0, N - 1, 0);
for (int i = 0; i < queries.size(); i++) {
if (queries[i][0] == 1) {
int l = queries[i][1];
int r = queries[i][2];
int x = range_queries(l, r, 0,
N - 1, 0);
ans.push_back(x);
}
else {
update(0, N - 1, 0, queries[i][1],
queries[i][2]);
}
}
return ans;
}
// Driver Code
int main()
{
// Consider 0 based indexing
int arr[] = { 25, 2, 7, 30, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
vector<vector<int> > queries{ { 1, 1, 4 },
{ 2, 2, 6 },
{ 1, 0, 3 } };
vector<int> ans = count(arr, N, queries);
for (int x : ans)
cout << x << " ";
return 0;
}
Python3
# python3 code to count primorials
# in the given range for Q queries
mxx = int(1e6 + 3)
isPrime = [True for _ in range(1000)]
segment = [0 for _ in range(4 * mxx)]
primorial = {}
# Mark true all prime numbers
def sieve():
global mxx, isprime, segment, primorial
isPrime[0] = isPrime[1] = False
for i in range(2, 1000):
if (isPrime[i]):
for j in range(2*i, 1000, i):
# Mark false which are the
# multiple of prime numbers
isPrime[j] = False
# Store primorials
def store_primorials():
global mxx, isprime, segment, primorial
cnt = 0
product = 1
for i in range(2, mxx):
if cnt >= 15:
break
if (isPrime[i]):
product = product * i
primorial[product] = primorial[product] + \
1 if product in primorial else 1
cnt += 1
# To build segment tree
def build(arr, low, high, ind):
global mxx, isprime, segment, primorial
# The node is leaf node
if (low == high):
# If array value is primorial
# assign leaf node value 1
# otherwise 0
if (arr[low] in primorial):
segment[ind] = 1
else:
segment[ind] = 0
return
mid = (low + high) >> 1
# Go to the left and right child of
# current node
build(arr, low, mid, 2 * ind + 1)
build(arr, mid + 1, high, 2 * ind + 2)
# Calculate count of primorials for
# internal node of segment tree for
# corresponding ranges
segment[ind] = segment[2 * ind + 1] + segment[2 * ind + 2]
# To update segment tree nodes
def update(low, high, ind, pos, val):
global mxx, isprime, segment, primorial
if (low == high):
# If new assign value is primorial
# then mark it 1 otherwise 0
if (val in primorial):
segment[ind] = 1
else:
segment[ind] = 0
return
mid = (low + high) >> 1
# Go to the left child if pos is on
# the left side of current node
if (pos >= low and pos <= mid):
update(low, mid, 2 * ind + 1,
pos, val)
# Go to the right child if pos is on
# the right side
else:
update(mid + 1, high, 2 * ind + 2,
pos, val)
# Update all internal nodes of segment
# tree
segment[ind] = segment[2 * ind + 1] + segment[2 * ind + 2]
# To compute answer for given range l to r
def range_queries(l, r, low, high, ind):
global mxx, isprime, segment, primorial
# [l, r] is given range, [low, high] is
# current range if current range is
# invalid return 0
if (high < l or low > r):
return 0
# If current range is completely inside of
# the given range then return value of
# that node
if (low >= l and high <= r):
return segment[ind]
mid = (low + high) >> 1
# Go to the left child and right child
# to compute answer
return (
range_queries(l, r, low, mid,
2 * ind + 1)
+ range_queries(l, r, mid + 1, high,
2 * ind + 2))
# Function to find the count of primorials
def count(arr, N, queries):
global mxx, isprime, segment, primorial
ans = []
# Mark prime numbers as a true
sieve()
# To precompute primorials
store_primorials()
# Build segment tree for given array
build(arr, 0, N - 1, 0)
for i in range(0, len(queries)):
if (queries[i][0] == 1):
l = queries[i][1]
r = queries[i][2]
x = range_queries(l, r, 0,
N - 1, 0)
ans.append(x)
else:
update(0, N - 1, 0, queries[i][1],
queries[i][2])
return ans
# Driver Code
if __name__ == "__main__":
# Consider 0 based indexing
arr = [25, 2, 7, 30, 1]
N = len(arr)
queries = [[1, 1, 4], [2, 2, 6], [1, 0, 3]]
ans = count(arr, N, queries)
for x in ans:
print(x, end=" ")
# This code is contributed by rakeshsahni
Javascript
<script>
// JavaScript code to count primorials
// in the given range for Q queries
let mxx = 1e6 + 3;
var isPrime = new Array(1000).fill(true);
var segment = new Array(4 * mxx).fill(0);
var primorial = {};
// Mark true all prime numbers
function sieve()
{
isPrime[0] = false;
isPrime[1] = false;
for (var i = 2; i < 1000; i++) {
if (isPrime[i]) {
for (var j = 2 * i; j < 1000; j = j + i)
// Mark false which are the
// multiple of prime numbers
isPrime[j] = false;
}
}
}
// Store primorials
function store_primorials()
{
var cnt = 0;
var product = 1;
for (var i = 2; i < mxx && cnt < 15; i++) {
if (isPrime[i]) {
product = product * 1 * i;
if (primorial.hasOwnProperty(product))
primorial[product]++;
else
primorial[product] = 1;
cnt++;
}
}
}
// To build segment tree
function build(arr, low, high, ind)
{
// The node is leaf node
if (low == high) {
// If array value is primorial
// assign leaf node value 1
// otherwise 0
if (primorial.hasOwnProperty(arr[low]))
segment[ind] = 1;
else
segment[ind] = 0;
return;
}
var mid = (low + high) >> 1;
// Go to the left and right child of
// current node
build(arr, low, mid, 2 * ind + 1);
build(arr, mid + 1, high, 2 * ind + 2);
// Calculate count of primorials for
// internal node of segment tree for
// corresponding ranges
segment[ind]
= segment[2 * ind + 1] + segment[2 * ind + 2];
}
// To update segment tree nodes
function update(low, high, ind, pos, val)
{
if (low == high) {
// If new assign value is primorial
// then mark it 1 otherwise 0
if (primorial.hasOwnProperty(low))
segment[ind] = 1;
else
segment[ind] = 0;
return;
}
var mid = (low + high) >> 1;
// Go to the left child if pos is on
// the left side of current node
if (pos >= low && pos <= mid)
update(low, mid, 2 * ind + 1, pos, val);
// Go to the right child if pos is on
// the right side
else
update(mid + 1, high, 2 * ind + 2, pos, val);
// Update all internal nodes of segment
// tree
segment[ind]
= segment[2 * ind + 1] + segment[2 * ind + 2];
}
// To compute answer for given range l to r
function range_queries(l, r, low, high, ind)
{
// [l, r] is given range, [low, high] is
// current range if current range is
// invalid return 0
if (high < l || low > r)
return 0;
// If current range is completely inside of
// the given range then return value of
// that node
if (low >= l && high <= r)
return segment[ind];
var mid = (low + high) >> 1;
// Go to the left child and right child
// to compute answer
return (
range_queries(l, r, low, mid, 2 * ind + 1)
+ range_queries(l, r, mid + 1, high, 2 * ind + 2));
}
// Function to find the count of primorials
function count(arr, N, queries)
{
var ans = [];
// Mark prime numbers as a true
sieve();
// To precompute primorials
store_primorials();
// Build segment tree for given array
build(arr, 0, N - 1, 0);
for (var i = 0; i < queries.length; i++) {
if (queries[i][0] == 1) {
var l = queries[i][1];
var r = queries[i][2];
var x = range_queries(l, r, 0, N - 1, 0);
ans.push(x);
}
else {
update(0, N - 1, 0, queries[i][1],
queries[i][2]);
}
}
return ans;
}
// Driver Code
// Consider 0 based indexing
var arr = [ 25, 2, 7, 30, 1 ];
var N = arr.length;
var queries = [ [ 1, 1, 4 ], [ 2, 2, 6 ], [ 1, 0, 3 ] ];
var ans = count(arr, N, queries);
for (var i = 0; i < ans.length; i++)
document.write(ans[i] + " ");
// This code is contributed by phasing17
</script>
2 3
Complejidad de tiempo: O(Q * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por patilnainesh911 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA