Dada una array arr[ ] que contiene N enteros positivos y un entero K y un vector de consultas Q . Se pueden realizar dos tipos de consultas:
- En la consulta de tipo 1 , todos los elementos del índice l a r aumentan con el valor X. El formato de entrada de esta consulta: 1 lrx
- En la consulta de tipo 2, para un entero K dado, imprima el recuento de todos los restos posibles si los elementos del índice l a r se dividen por k. El formato de entrada de esta consulta: 2 lr
Ejemplos:
Entrada: arr[ ] = {7, 13, 5, 9, 16, 21}, K=4, vector< vector< int > >Q = { {2, 3, 5}, { 1, 0, 4, 1 }, {2, 2, 5} }
Salida: 1 2 0 0
0 2 2 0
Explicación : El primer tipo de consulta es 2. Entonces , para el índice 3 a 5, solo hay un elemento => (16) cuyo resto es 0 para dado k=4. Dos elementos cuyo resto es 1 => ( 9, 21 ). No hay ningún elemento cuyo resto sea 2 o 3.
Después de la segunda consulta, será: {8, 14, 6, 10, 17, 21}. debido a que todos los elementos de la array se incrementan en 1 .
En la tercera consulta para el índice 2 a 5, hay dos elementos cuyos residuos son 1 (17, 21) y 2 (6, 10). No hay elementos cuyo resto sea 0 o 3.Entrada : arr[ ] = {6, 7, 8, 9, 10, 11}, k=5, vector< vector< int > >Q = { {2, 1, 1 } {2, 1, 3}, { 1, 1, 3, 2}, {2, 1, 3} }
Salida : 0 0 1 0 0
0 0 1 1 1
1 1 0 0 1
Enfoque ingenuo: un enfoque simple es en la consulta de actualización, solo iterar a través de una array en un rango dado y actualizar el valor. Y para otro tipo de consulta, itere a través del rango dado y tome mod con k, mantenga la array hash para almacenar un recuento particular de ese resto. Pero la complejidad temporal de este método es O(N*Q*k)
Complejidad de tiempo: O(N*Q*k)
Espacio auxiliar: O(k), para mantener una array hash de tamaño k
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el árbol de segmentos y la propagación perezosa , según la siguiente idea:
Intuición:
Aquí el número de consultas es alto y también hay consultas en las que se debe actualizar un rango de l a r. También tenemos que imprimir respuestas para el rango dado de l a r.
Por lo tanto, estos dan sugerencias para usar el árbol de segmentos con propagación diferida , porque en este método podemos responder cada consulta en tiempo O (log (N)), es decir (Altura del árbol de segmentos). Junto con esto, usaremos la propagación diferida para actualizar los valores de rango de manera eficiente, porque en la propagación diferida, solo actualizamos el Node del árbol de segmentos que se requiere actualmente y propagará el valor al Node secundario, y actualizará este Node secundario, siempre que sea necesario.
Para almacenar este valor de propagación,
- Use una array llamada perezosa (código de verificación) en lugar de un valor dado,
- Simplemente actualice un rango con val%k, porque el enfoque principal es el resto y esto no afectará la respuesta.
- Use un árbol de segmentos 2D, de modo que cada Node del árbol de segmentos contenga una array de longitud K, para almacenar el recuento de todos los restos posibles.
Ilustración:
Para arr[]={1, 2, 5}, k=4, el árbol de segmentos se ve así:
así que básicamente el segmento de Node [ ind ] [ j ] contendrá el recuento de elementos cuyo resto es j correspondiente a un rango cubierto por el índice ind th del árbol de segmentos.
En otras palabras, si el ind -ésimo índice del árbol de segmento cubre el rango de a a b de la array, entonces segment[ ind ][ 0 ] representa, el conteo de elementos cuyo resto es 0 en el rango de a a b.
De manera similar, segment[ ind ][ j ] representará el recuento de elementos cuyo resto es j para K dado en el rango de a a b.
Aquí, el truco principal es que si cualquier rango se actualiza por el valor x, entonces todos los elementos de la array de longitud K que se adjunta con el Node del árbol del segmento, harán el cambio cíclico correcto en x% k posiciones.
Supongamos que si cualquier valor de rango se incrementa en 1, significa el conteo de elementos cuyo resto era 0 ahora se convierte en el conteo de elementos cuyo resto es 1.Antes de modificar ese Node, almacene el valor en la array temporal.
Después de eso, modifique el Node del árbol de segmentos por segmento[ ind ][ (val+i)%k ]=temp[ i ]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for Find count of all
// possible remainders for given integer K
// in the given ranges for Q queries.
#include <bits/stdc++.h>
using namespace std;
#define MXX 100001
// to store propagate value
int lazy[4 * MXX];
int segment[4 * MXX][51];
int ans[51];
// build segment tree for given arr
void build(int arr[], int low, int high, int ind, int k)
{
if (low == high) {
int rem = arr[low] % k;
// mark 1 at ind corresponding to remainder
segment[ind][rem] = 1;
return;
}
int mid = (low + high) >> 1;
build(arr, low, mid, 2 * ind + 1, k);
build(arr, mid + 1, high, 2 * ind + 2, k);
// before returning, compute answer for
// all possible remainders for node ind
for (int i = 0; i < k; i++) {
segment[ind][i] = segment[2 * ind + 1][i]
+ segment[2 * ind + 2][i];
}
}
// to update a range l to r
void update(int l, int r, int low, int high, int ind, int k,
int val)
{
lazy[ind] %= k;
// if any value is pending than update it
if (lazy[ind] != 0) {
if (low != high) {
// propagate pending value to its children
lazy[2 * ind + 1] += lazy[ind];
lazy[2 * ind + 2] += lazy[ind];
lazy[2 * ind + 1] %= k;
lazy[2 * ind + 2] %= k;
}
int incr = lazy[ind];
// make temporary vector to store value
// so we can perform cycle operation without
// loosing actual values
vector<int> temp(k);
for (int i = 0; i < k; i++) {
temp[i] = segment[ind][i];
}
// do cyclic shift operation
for (int i = 0; i < k; i++) {
segment[ind][(incr + i) % k] = temp[i];
}
// after done pending update mark it 0.
lazy[ind] = 0;
}
// invalid range then return
if (high < low || low > r || high < l)
return;
// the current range is subset of
// our actual range so update value
if (low >= l && high <= r) {
val %= k;
vector<int> temp(k);
for (int i = 0; i < k; i++) {
temp[i] = segment[ind][i];
}
for (int i = 0; i < k; i++) {
segment[ind][(val + i) % k] = temp[i];
}
if (low != high) {
lazy[2 * ind + 1] += val;
lazy[2 * ind + 2] += val;
lazy[2 * ind + 1] %= k;
lazy[2 * ind + 2] %= k;
}
return;
}
int mid = (low + high) >> 1;
// go to left and right side
update(l, r, low, mid, 2 * ind + 1, k, val);
update(l, r, mid + 1, high, 2 * ind + 2, k, val);
// after updating and before returning,
// calculate answer
for (int i = 0; i < k; i++) {
segment[ind][i] = segment[2 * ind + 1][i]
+ segment[2 * ind + 2][i];
}
}
// to compute answer of a query
// most of operation are same as update function
void query(int l, int r, int low, int high, int ind, int k)
{
lazy[ind] %= k;
if (lazy[ind] != 0) {
if (low != high) {
lazy[2 * ind + 1] += lazy[ind];
lazy[2 * ind + 2] += lazy[ind];
lazy[2 * ind + 1] %= k;
lazy[2 * ind + 2] %= k;
}
int incr = lazy[ind];
vector<int> temp(k);
for (int i = 0; i < k; i++) {
temp[i] = segment[ind][i];
}
for (int i = 0; i < k; i++) {
segment[ind][(incr + i) % k] = temp[i];
}
lazy[ind] = 0;
}
if (high < low || low > r || high < l)
return;
// this range is subset of our actual
// require range so compute answer for
// this range
if (low >= l && high <= r) {
for (int i = 0; i < k; i++)
ans[i] += segment[ind][i];
return;
}
int mid = (low + high) >> 1;
query(l, r, low, mid, 2 * ind + 1, k);
query(l, r, mid + 1, high, 2 * ind + 2, k);
}
// after printing answer
// reset ans array
void print(int k)
{
for (int i = 0; i < k; i++)
cout << ans[i] << " ";
cout << "\n";
}
void reset()
{
for (int i = 0; i < 51; i++)
ans[i] = 0;
}
int main()
{
int arr[] = { 7, 13, 5, 9, 16, 21 };
int n = sizeof(arr) / sizeof(arr[0]);
int q = 3, k = 4;
// build segment tree
build(arr, 0, n - 1, 0, k);
// first query
int x, l = 3, r = 5;
query(l, r, 0, n - 1, 0, k);
print(k);
reset();
// second query
l = 0, r = 4, x = 1;
update(l, r, 0, n - 1, 0, k, x);
// third query
l = 2, r = 5;
query(l, r, 0, n - 1, 0, k);
print(k);
reset();
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for Find count of all
// possible remainders for given integer K
// in the given ranges for Q queries.
class GFG{
public static int MXX = 100001;
// to store propagate value
public static int lazy[] = new int[4 * MXX];
public static int segment[][] = new int[4 * MXX][51];
public static int ans[] = new int[51];
// build segment tree for given arr
public static void build(int arr[], int low, int high, int ind, int k)
{
if (low == high) {
int rem = arr[low] % k;
// mark 1 at ind corresponding to remainder
segment[ind][rem] = 1;
return;
}
int mid = (low + high) >> 1;
build(arr, low, mid, 2 * ind + 1, k);
build(arr, mid + 1, high, 2 * ind + 2, k);
// before returning, compute answer for
// all possible remainders for node ind
for (int i = 0; i < k; i++) {
segment[ind][i] = segment[2 * ind + 1][i] + segment[2 * ind + 2][i];
}
}
// to update a range l to r
public static void update(int l, int r, int low, int high, int ind, int k, int val)
{
lazy[ind] %= k;
// if any value is pending than update it
if (lazy[ind] != 0) {
if (low != high) {
// propagate pending value to its children
lazy[2 * ind + 1] += lazy[ind];
lazy[2 * ind + 2] += lazy[ind];
lazy[2 * ind + 1] %= k;
lazy[2 * ind + 2] %= k;
}
int incr = lazy[ind];
// make temporary array to store value
// so we can perform cycle operation without
// loosing actual values
int temp[] = new int[k];
for (int i = 0; i < k; i++) {
temp[i] = segment[ind][i];
}
// do cyclic shift operation
for (int i = 0; i < k; i++) {
segment[ind][(incr + i) % k] = temp[i];
}
// after done pending update mark it 0.
lazy[ind] = 0;
}
// invalid range then return
if (high < low || low > r || high < l){
return;
}
// the current range is subset of
// our actual range so update value
if (low >= l && high <= r) {
val %= k;
int temp[] = new int[k];
for (int i = 0; i < k; i++) {
temp[i] = segment[ind][i];
}
for (int i = 0 ; i < k ; i++) {
segment[ind][(val + i) % k] = temp[i];
}
if (low != high) {
lazy[2 * ind + 1] += val;
lazy[2 * ind + 2] += val;
lazy[2 * ind + 1] %= k;
lazy[2 * ind + 2] %= k;
}
return;
}
int mid = (low + high) >> 1;
// go to left and right side
update(l, r, low, mid, 2 * ind + 1, k, val);
update(l, r, mid + 1, high, 2 * ind + 2, k, val);
// after updating and before returning,
// calculate answer
for (int i = 0; i < k; i++) {
segment[ind][i] = segment[2 * ind + 1][i]
+ segment[2 * ind + 2][i];
}
}
// to compute answer of a query
// most of operation are same as update function
public static void query(int l, int r, int low, int high, int ind, int k)
{
lazy[ind] %= k;
if (lazy[ind] != 0) {
if (low != high) {
lazy[2 * ind + 1] += lazy[ind];
lazy[2 * ind + 2] += lazy[ind];
lazy[2 * ind + 1] %= k;
lazy[2 * ind + 2] %= k;
}
int incr = lazy[ind];
int temp[] = new int[k];
for (int i = 0 ; i < k ; i++) {
temp[i] = segment[ind][i];
}
for (int i = 0 ; i < k ; i++) {
segment[ind][(incr + i) % k] = temp[i];
}
lazy[ind] = 0;
}
if (high < low || low > r || high < l)
return;
// this range is subset of our actual
// require range so compute answer for
// this range
if (low >= l && high <= r) {
for (int i = 0 ; i < k ; i++){
ans[i] += segment[ind][i];
}
return;
}
int mid = (low + high) >> 1;
query(l, r, low, mid, 2 * ind + 1, k);
query(l, r, mid + 1, high, 2 * ind + 2, k);
}
// after printing answer
// reset ans array
public static void print(int k)
{
for (int i = 0; i < k; i++)
System.out.print(ans[i] + " ");
System.out.println("");
}
public static void reset()
{
for (int i = 0; i < 51; i++){
ans[i] = 0;
}
}
// Driver code
public static void main(String args[])
{
int arr[] = {7, 13, 5, 9, 16, 21};
int n = arr.length;
int q = 3, k = 4;
// build segment tree
build(arr, 0, n-1, 0, k);
// first query
int x, l = 3, r = 5;
query(l, r, 0, n-1, 0, k);
print(k);
reset();
// second query
l = 0;
r = 4;
x = 1;
update(l, r, 0, n-1, 0, k, x);
// third query
l = 2;
r = 5;
query(l, r, 0, n-1, 0, k);
print(k);
reset();
}
}
// This code is contributed by subhamgoyal2014.
Python3
# program for Find count of all # possible remainders for given integer K # in the given ranges for Q queries. MXX = 100001 # to store propagate value lazy = [0]*(4*MXX) segment = [[0 for i in range(51)] for i in range(4*MXX)] ans = [0]*51 # build segment tree for given arr def build(arr, low, high, ind, k): if low == high: rem = arr[low] % k # mark 1 at ind corresponding to remainder segment[ind][rem] = 1 return mid = (low+high) >> 1 build(arr, low, mid, 2*ind+1, k) build(arr, mid+1, high, 2*ind+2, k) # Before returning, compute answer for # all possible remainders for node ind for i in range(k): segment[ind][i] = segment[2*ind+1][i]+segment[2*ind+2][i] # function to update a range l to r def update(l, r, low, high, ind, k, val): lazy[ind] %= k # if any value is pending than update it if lazy[ind] != 0: if low != high: # propagate pending value to its children lazy[2*ind+1] += lazy[ind] lazy[2*ind+2] += lazy[ind] lazy[2*ind+1] %= k lazy[2*ind+2] %= k incr = lazy[ind] # make temporary vector to store value # so we can perform cycle operation without # loosing actual values temp = [0]*k for i in range(k): temp[i] = segment[ind][i] # do cyclic shift operation for i in range(k): segment[ind][(incr+1) % k] = temp[i] # after done pending update mark it 0. lazy[ind] = 0 # invalid range then return if high < low or low > r or high < l: return # the current range is subset of # our actual range so update value if low >= l and high <= r: val %= k temp = [0]*k for i in range(k): temp[i] = segment[ind][i] for i in range(k): segment[ind][(val+i) % k] = temp[i] if low != high: lazy[2 * ind + 1] += val lazy[2 * ind + 2] += val lazy[2 * ind + 1] %= k lazy[2 * ind + 2] %= k return mid = (low+high) >> 1 # go to left and right side update(l, r, low, mid, 2*ind+1, k, val) update(l, r, mid+1, high, 2*ind+2, k, val) # after updating and before returning, calculate answer for i in range(k): segment[ind][i] = segment[2*ind+1][i]+segment[2*ind+2][i] # to compute answer of a query # most of operation are same as update function def query(l, r, low, high, ind, k): lazy[ind] %= k if lazy[ind] != 0: if low != high: lazy[2 * ind + 1] += lazy[ind] lazy[2 * ind + 2] += lazy[ind] lazy[2 * ind + 1] %= k lazy[2 * ind + 2] %= k incr = lazy[ind] temp = [0]*k for i in range(k): temp[i] = segment[ind][i] for i in range(k): segment[ind][(incr+i) % k] = temp[i] lazy[ind] = 0 if high < low or low > r or high < l: return # this range is subset of our actual # require range so compute answer for # this range if low >= l and high <= r: for i in range(k): ans[i] += segment[ind][i] return mid = (low+high) >> 1 query(l, r, low, mid, 2*ind+1, k) query(l, r, mid+1, high, 2*ind+2, k) # after printing answer # reset ans array def printing(k): for i in range(int(k)): print(ans[i], end=" ") print() def reset(): for i in range(51): ans[i] = 0 # Driver Code if __name__ == '__main__': arr = [7, 13, 5, 9, 16, 21, 33, 12, 19] n = len(arr) q = 3 k = 4 # build segment tree build(arr, 0, n - 1, 0, k) # first query x = 0 l = 3 r = 5 query(l, r, 0, n-1, 0, k) printing(k) reset() # second query l = 0 r = 4 x = 1 update(l, r, 0, n - 1, 0, k, x) # third query l = 2 r = 5 query(l, r, 0, n - 1, 0, k) printing(k) reset() '''This Code is contributed by RAJAT KUMAR'''
1 2 0 0 0 2 2 0
Complejidad de tiempo : O(Q*K*logN)
Espacio auxiliar : O(N*K)
Publicación traducida automáticamente
Artículo escrito por patilnainesh911 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA