Dada una array A de N enteros. Debe responder dos tipos de consultas:
1. Actualizar [l, r]: para cada i en el rango de l a r, actualice A i con D (A i ), donde D (A i ) representa el número de divisores de A i
2. Consulta [l, r]: calcule la suma de todos los números comprendidos entre l y r en la array A.
La entrada se proporciona como dos números enteros N y Q, que representan el número de enteros en la array y el número de consultas, respectivamente. La siguiente línea contiene una array de n enteros seguida de Q consultas donde la i-ésima consulta se representa como tipo i , li , r i .
Requisito previo: árboles indexados binarios | Árboles de segmento
Ejemplos:
Input : 7 4
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
Output : 30
13
4
Explicación: la primera consulta es para calcular la suma de números de A 1 a A 7 , que es 6 + 4
+ 1 + 10 + 3 + 2 + 4 = 30. De manera similar, la segunda consulta da como resultado 13. Para la tercera consulta,
que es actualizar operación, por lo tanto, A 3 seguirá siendo 1, A 4 se convertirá en 4 y A 5 se convertirá en 2. La
cuarta consulta dará como resultado A 4 = 4.
Enfoque ingenuo:
una solución simple es ejecutar un ciclo de l a r y calcular la suma de los elementos en un rango dado. Para actualizar un valor, calcule previamente los valores del número de divisores de cada número y simplemente haga arr[i] = divisores[arr[i]].
Enfoque eficiente:
La idea es reducir la complejidad del tiempo para cada consulta y actualizar la operación a O(logN). Utilice árboles indexados binarios (BIT) o árboles de segmentos. Construya una array BIT[] y tenga dos funciones para la operación de consulta y actualización y calcule previamente la cantidad de divisores para cada número. Ahora, para cada operación de actualización, la observación clave es que los números ‘1’ y ‘2’ tendrán ‘1’ y ‘2’ como su número de divisores respectivamente, por lo que si existe en el rango de consulta de actualización, no t necesita ser actualizado. Usaremos un conjunto para almacenar el índice de solo aquellos números que son mayores que 2 y usaremos la búsqueda binaria para encontrar el índice l de la consulta de actualización e incrementar el índice l hasta que cada elemento se actualice en el rango de esa consulta de actualización. Si el arr[i] tiene solo 2 divisores, luego de actualizarlo, elimínelo del conjunto, ya que siempre será 2, incluso después de cualquier consulta de actualización siguiente. Para la operación de consulta de suma, simplemente haga consulta (r) – consulta (l – 1).
// CPP program to calculate sum
// in an interval and update with
// number of divisors
#include <bits/stdc++.h>
using namespace std;
int divisors[100], BIT[100];
// structure for queries with members type,
// leftIndex, rightIndex of the query
struct queries
{
int type, l, r;
};
// function to calculate the number
// of divisors of each number
void calcDivisors()
{
for (int i = 1; i < 100; i++) {
for (int j = i; j < 100; j += i) {
divisors[j]++;
}
}
}
// function for updating the value
void update(int x, int val, int n)
{
for (x; x <= n; x += x&-x) {
BIT[x] += val;
}
}
// function for calculating the required
// sum between two indexes
int sum(int x)
{
int s = 0;
for (x; x > 0; x -= x&-x) {
s += BIT[x];
}
return s;
}
// function to return answer to queries
void answerQueries(int arr[], queries que[], int n, int q)
{
// Declaring a Set
set<int> s;
for (int i = 1; i < n; i++) {
// inserting indexes of those numbers
// which are greater than 2
if(arr[i] > 2) s.insert(i);
update(i, arr[i], n);
}
for (int i = 0; i < q; i++) {
// update query
if (que[i].type == 1) {
while (true) {
// find the left index of query in
// the set using binary search
auto it = s.lower_bound(que[i].l);
// if it crosses the right index of
// query or end of set, then break
if(it == s.end() || *it > que[i].r) break;
que[i].l = *it;
// update the value of arr[i] to
// its number of divisors
update(*it, divisors[arr[*it]] - arr[*it], n);
arr[*it] = divisors[arr[*it]];
// if updated value becomes less than or
// equal to 2 remove it from the set
if(arr[*it] <= 2) s.erase(*it);
// increment the index
que[i].l++;
}
}
// sum query
else {
cout << (sum(que[i].r) - sum(que[i].l - 1)) << endl;
}
}
}
// Driver Code
int main()
{
// precompute the number of divisors for each number
calcDivisors();
int q = 4;
// input array
int arr[] = {0, 6, 4, 1, 10, 3, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
// declaring array of structure of type queries
queries que[q + 1];
que[0].type = 2, que[0].l = 1, que[0].r = 7;
que[1].type = 2, que[1].l = 4, que[1].r = 5;
que[2].type = 1, que[2].l = 3, que[2].r = 5;
que[3].type = 2, que[3].l = 4, que[3].r = 4;
// answer the Queries
answerQueries(arr, que, n, q);
return 0;
}
30 13 4
La Complejidad de Tiempo para responder consultas Q será O(Q * log(N)).
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA