Dada una array arr[] de N enteros y un número de consultas Q . La tarea consiste en responder a tres tipos de consultas.
- Actualizar [l, r] : por cada i en el rango [l, r] incremente arr[i] en 1 .
- Actualizar [l, val] : cambia el valor de arr[l] a val .
- Consulta [l, r] – ¡calcula la suma de arr[i]! % 10 9 para todo i en el rango [l, r] donde arr[i]! es el factorial de arr[i] .
Requisito previo: árboles indexados binarios | Ejemplos de árboles de segmentos :
Entrada: Q = 6, arr[] = { 1, 2, 1, 4, 5 } 3 1 5 1 1 3 2 2 4 3 2 4 1 2 5 3 1 5 Salida: 148 50 968 1 a consulta, la requerida suma es (1! + 2! + 1! + 4! + 5!) % 10 9 = 148 2ª consulta, la array se convierte en arr[] = { 2, 3, 2, 4, 5 } 3ª consulta, array se convierte en arr[] = { 2, 4, 2, 4, 5 } 4 a consulta, la suma requerida es (4! + 2! + 4!) % 10 9 = 50 5 a consulta, la array se convierte en arr[] = { 2, 5, 3, 5, 6 } 6 a consulta, la suma requerida es (2! + 5! + 3! + 5! + 6!) % 10 9 = 968
Enfoque ingenuo: una solución simple es ejecutar un ciclo de l a r y calcular la suma del factorial de los elementos (precalculados) en el rango dado para la tercera consulta . Para la segunda consulta , para actualizar un valor, simplemente reemplace arr[i] con el valor dado, es decir, arr[i] = val . Para la consulta de primer tipo, incremente el valor de arr[i], es decir , arr[i] = arr[i] + 1 . Enfoque eficiente: Se puede observar a partir de un análisis cuidadoso que 40! es divisible por 10 9 , es decir factorial de todo número mayor que40 será divisible por 10 9 . Por lo tanto, eso suma cero a nuestra respuesta para la tercera consulta . La idea es reducir la complejidad del tiempo para cada operación de consulta y actualizació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.
- Ahora, para cada operación de actualización del primer tipo , la observación clave es que el número en el rango dado puede actualizarse como máximo a 40 , ya que después de eso no importará, ya que agregará cero a nuestra respuesta final. Usaremos un conjunto para almacenar el índice de solo aquellos números que son menores que 10 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] se vuelve mayor o igual a 40 después de incrementarse en 1 , elimínelo del conjunto, ya que no afectará nuestra respuesta a la consulta de suma incluso después de cualquier consulta de actualización siguiente.
- Para la operación de actualización del segundo tipo , llame a la función de actualización con el valor dado. Además, el valor dado es < 40 , inserte el índice del elemento a reemplazar en el conjunto y si el valor dado es ≥ 40 , elimínelo del conjunto ya que no tendrá importancia en la consulta de suma.
- Para la consulta de suma del tercer tipo , simplemente haga query (r) – query(l – 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to calculate sum of
// factorials in an interval and update
// with two types of operations
#include <bits/stdc++.h>
using namespace std;
// Modulus
const int MOD = 1e9;
// Maximum size of input array
const int MAX = 100;
// Size for factorial array
const int SZ = 40;
int BIT[MAX + 1], fact[SZ + 1];
// structure for queries with members type,
// leftIndex, rightIndex of the query
struct queries {
int type, l, r;
};
// 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)
{
// Precomputing factorials
fact[0] = 1;
for (int i = 1; i < 41; i++)
fact[i] = (fact[i - 1] * i) % MOD;
// Declaring a Set
set<int> s;
for (int i = 1; i < n; i++) {
// inserting indexes of those
// numbers which are lesser
// than 40
if (arr[i] < 40) {
s.insert(i);
update(i, fact[arr[i]], n);
}
else
update(i, 0, n);
}
for (int i = 0; i < q; i++) {
// update query of the 1st type
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;
int val = arr[*it] + 1;
// update the value of arr[i] to
// its new value
update(*it, fact[val] - fact[arr[*it]], n);
arr[*it]++;
// if updated value becomes greater
// than or equal to 40 remove it from
// the set
if (arr[*it] >= 40)
s.erase(*it);
// increment the index
que[i].l++;
}
}
// update query of the 2nd type
else if (que[i].type == 2) {
int idx = que[i].l;
int val = que[i].r;
// update the value to its new value
update(idx, fact[val] - fact[arr[idx]], n);
arr[idx] = val;
// If the value is less than 40, insert
// it into set, otherwise remove it
if (val < 40)
s.insert(idx);
else
s.erase(idx);
}
// sum query of the 3rd type
else
cout << (sum(que[i].r) - sum(que[i].l - 1))
<< endl;
}
}
// Driver Code to test above functions
int main()
{
int q = 6;
// input array using 1-based indexing
int arr[] = { 0, 1, 2, 1, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// declaring array of structure of type queries
queries que[q + 1];
que[0].type = 3, que[0].l = 1, que[0].r = 5;
que[1].type = 1, que[1].l = 1, que[1].r = 3;
que[2].type = 2, que[2].l = 2, que[2].r = 4;
que[3].type = 3, que[3].l = 2, que[3].r = 4;
que[4].type = 1, que[4].l = 2, que[4].r = 5;
que[5].type = 3, que[5].l = 1, que[5].r = 5;
// answer the Queries
answerQueries(arr, que, n, q);
return 0;
}
Python3
# Python3 program to calculate sum of # factorials in an interval and update # with two types of operations from bisect import bisect_left as lower_bound # Modulus MOD = 1e9 # Maximum size of input array MAX = 100 # Size for factorial array SZ = 40 BIT = [0] * (MAX + 1) fact = [0] * (SZ + 1) # structure for queries with members type, # leftIndex, rightIndex of the query class queries: def __init__(self, tpe, l, r): self.type = tpe self.l = l self.r = r # function for updating the value def update(x, val, n): global BIT while x <= n: BIT[x] += val x += x & -x # function for calculating the required # sum between two indexes def summ(x): global BIT s = 0 while x > 0: s += BIT[x] x -= x & -x return s # function to return answer to queries def answerQueries(arr: list, que: list, n: int, q: int): global fact # Precomputing factorials fact[0] = 1 for i in range(1, 41): fact[i] = int((fact[i - 1] * i) % MOD) # Declaring a Set s = set() for i in range(1, n): # inserting indexes of those # numbers which are lesser # than 40 if arr[i] < 40: s.add(i) update(i, fact[arr[i]], n) else: update(i, 0, n) for i in range(q): # update query of the 1st type if que[i].type == 1: while True: s = list(s) s.sort() # find the left index of query in # the set using binary search it = lower_bound(s, que[i].l) # if it crosses the right index of # query or end of set, then break if it == len(s) or s[it] > que[i].r: break que[i].l = s[it] val = arr[s[it]] + 1 # update the value of arr[i] to # its new value update(s[it], fact[val] - fact[arr[s[it]]], n) arr[s[it]] += 1 # if updated value becomes greater # than or equal to 40 remove it from # the set if arr[s[it]] >= 40: s.remove(it) # increment the index que[i].l += 1 # update query of the 2nd type elif que[i].type == 2: s = set(s) idx = que[i].l val = que[i].r # update the value to its new value update(idx, fact[val] - fact[arr[idx]], n) arr[idx] = val # If the value is less than 40, insert # it into set, otherwise remove it if val < 40: s.add(idx) else: s.remove(idx) # sum query of the 3rd type else: print((summ(que[i].r) - summ(que[i].l - 1))) # Driver Code if __name__ == "__main__": q = 6 # input array using 1-based indexing arr = [0, 1, 2, 1, 4, 5] n = len(arr) # declaring array of structure of type queries que = [ queries(3, 1, 5), queries(1, 1, 3), queries(2, 2, 4), queries(3, 2, 4), queries(1, 2, 5), queries(3, 1, 5) ] # answer the Queries answerQueries(arr, que, n, q) # This code is contributed by # sanjeev2552
Javascript
// JavaScript program to calculate sum of
// factorials in an interval and update
// with two types of operations
// Modulus
let MOD = 10000000000;
// Maximum size of input array
let MAX = 100;
// Size for factorial array
let SZ = 40;
let BIT = new Array(MAX + 1).fill(0);
let fact = new Array(SZ + 1).fill(0);
function lower_bound(arr, ele)
{
for (var i = 0; i < arr.length; i++)
{
if (arr[i] >= ele)
return i;
}
return arr.length;
}
// structure for queries with members type,
// leftIndex, rightIndex of the query
class queries
{
constructor(tpe, l, r)
{
this.type = tpe;
this.l = l;
this.r = r;
}
}
// function for updating the value
function update(BIT, x, val, n)
{
while (x <= n)
{
BIT[x] += val;
x += (x & -x);
}
return BIT
}
// function for calculating the required
// sum between two indexes
function summ(x)
{
var s = 0;
while (x > 0)
{
s += BIT[x];
x -= x & -x;
}
return s;
}
// function to return answer to queries
function answerQueries(arr, que, n, q)
{
// Precomputing factorials
fact[0] = 1;
for (var i = 1; i <= 40; i++)
fact[i] = Number((fact[i - 1] * i) % MOD);
// Declaring a Set
var s = new Set();
for (var i = 1; i < n; i++)
{
// inserting indexes of those
// numbers which are lesser
// than 40
if (arr[i] < 40)
{
s.add(i);
BIT = update(BIT, i, fact[arr[i]], n);
}
else
BIT = update(BIT, i, 0, n);
}
for (var i = 0; i < q; i++)
{
// update query of the 1st type
if (que[i].type == 1)
{
while (true)
{
s = Array.from(s);
s.sort();
// find the left index of query in
// the set using binary search
it = lower_bound(s, que[i].l);
// if it crosses the right index of
// query or end of set, then break
if (it == s.length || s[it] > que[i].r)
break;
que[i].l = s[it];
val = arr[s[it]] + 1;
// update the value of arr[i] to
// its new value
BIT = update(BIT, s[it], fact[val] -
fact[arr[s[it]]], n);
arr[s[it]] += 1;
// if updated value becomes greater
// than or equal to 40 remove it from
// the set
if (arr[s[it]] >= 40)
s.splice(it, 1);
// increment the index
que[i].l += 1;
}
}
// update query of the 2nd type
else if (que[i].type == 2)
{
s = new Set(s);
var idx = que[i].l;
var val = que[i].r;
//update the value to its new value
BIT = update(BIT, idx, fact[val] - fact[arr[idx]], n);
arr[idx] = val;
// If the value is less than 40, insert
// it into set, otherwise remove it
if (val < 40)
s.add(idx);
else
s.remove(idx);
}
// sum query of the 3rd type
else
console.log((summ(que[i].r) - summ(que[i].l - 1)));
}
}
// Driver Code
let q = 6;
// input array using 1-based indexing
let arr = [0, 1, 2, 1, 4, 5];
let n = arr.length;
// declaring array of structure of type queries
let que = [ new queries(3, 1, 5), new queries(1, 1, 3),
new queries(2, 2, 4),
new queries(3, 2, 4),
new queries(1, 2, 5),
new queries(3, 1, 5) ];
// answer the Queries
answerQueries(arr, que, n, q);
// This code is contributed by phasing17
Producción:
148 50 968
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