Dada una array arr[] de N elementos, la tarea es responder Q consultas, cada una de las cuales tiene dos números enteros L y R. Para cada consulta, la tarea es encontrar el número de elementos en el subarreglo arr[L…R] cuya suma de dígitos es par.
Ejemplos:
Entrada: arr[] = {7, 3, 19, 13, 5, 4}
consulta = { {1, 5}, {0, 1} }
Salida: 3
Explicación:
Consulta 1: Los elementos 19, 13 y 4 tienen par suma de dígitos en el subarreglo: {3, 9, 13, 5, 4}.
Consulta 2: ningún elemento tiene una suma par en el subarreglo: {7, 3}Entrada: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}
consulta = { 3, 5 }
Salida: 1
Ya hemos discutido este enfoque: consultas para el recuento de elementos de suma de dígitos pares en el rango dado usando el árbol de segmentos
Enfoque: (usando el algoritmo de MO )
La idea es preprocesar todas las consultas para que el resultado de una consulta se pueda usar en la siguiente consulta.
- Ordene todas las consultas de manera que las consultas con valores L de 0 a √n – 1 se junten, seguidas de las consultas de √n a 2×√n – 1 , y así sucesivamente. Todas las consultas dentro de un bloque se clasifican en orden creciente de valores R.
- Procese todas las consultas una por una y aumente el recuento de elementos de suma de dígitos pares y almacene el resultado en la estructura.
- Deje que count_even almacene el recuento de elementos de suma de dígitos pares en la consulta anterior.
- Elimine elementos adicionales de la consulta anterior y agregue nuevos elementos para la consulta actual. Por ejemplo, si la consulta anterior fue [0, 8] y la consulta actual es [3, 9], elimine los elementos arr[0], arr[1] y arr[2] y agregue arr[9].
- Para mostrar los resultados, ordene las consultas en el orden en que se proporcionaron.
Funciones auxiliares:
agregar elements()
- Si el elemento actual tiene una suma de dígitos pares, aumente el recuento de count_even .
Eliminando elements()
- Si el elemento actual tiene una suma de dígitos pares, disminuya el recuento de count_even .
El siguiente código es la implementación del enfoque anterior:
C++
// C++ program to count of even
// digit sum elements in the given
// range using MO's algorithm
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
// Variable to represent block size.
// This is made global so compare()
// of sort can use it.
int block;
// Structure to represent a query range
struct Query {
// Starting index
int L;
// Ending index
int R;
// Index of query
int index;
// Count of even
// even digit sum
int even;
};
// To store the count of
// even digit sum
int count_even;
// Function used to sort all queries so that
// all queries of the same block are arranged
// together and within a block, queries are
// sorted in increasing order of R values.
bool compare(Query x, Query y)
{
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block < y.L / block;
// Same block, sort by R value
return x.R < y.R;
}
// Function used to sort all queries
// in order of their index value so that
// results of queries can be printed
// in same order as of input
bool compare1(Query x, Query y)
{
return x.index < y.index;
}
// Function to find the digit sum
// for a number
int digitSum(int num)
{
int sum = 0;
while (num) {
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to Add elements
// of current range
void add(int currL, int a[])
{
// If digit sum of a[currL]
// is even then increment
if (digitSum(a[currL]) % 2 == 0)
count_even++;
}
// Function to remove elements
// of previous range
void remove(int currR, int a[])
{
// If digit sum of a[currL]
// is even then decrement
if (digitSum(a[currR]) % 2 == 0)
count_even--;
}
// Function to generate
// the result of queries
void queryResults(int a[], int n,
Query q[], int m)
{
// Initialize number of
// even digit sum to 0
count_even = 0;
// Find block size
block = (int)sqrt(n);
// Sort all queries so that queries of
// same blocks are arranged together.
sort(q, q + m, compare);
// Initialize current L, current R and
// current result
int currL = 0, currR = 0;
for (int i = 0; i < m; i++) {
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Add Elements of current range
while (currR <= R) {
add(currR, a);
currR++;
}
while (currL > L) {
add(currL - 1, a);
currL--;
}
// Remove element of previous range
while (currR > R + 1)
{
remove(currR - 1, a);
currR--;
}
while (currL < L) {
remove(currL, a);
currL++;
}
q[i].even = count_even;
}
}
// Function to display the results of
// queries in their initial order
void printResults(Query q[], int m)
{
sort(q, q + m, compare1);
for (int i = 0; i < m; i++) {
cout << q[i].even << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 5, 2, 3, 1, 4, 8, 10, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
Query q[] = { { 1, 3, 0, 0 },
{ 0, 4, 1, 0 },
{ 4, 7, 2, 0 } };
int m = sizeof(q) / sizeof(q[0]);
queryResults(arr, n, q, m);
printResults(q, m);
return 0;
}
Java
// Java program to count of even
// digit sum elements in the given
// range using MO's algorithm
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
class GFG{
static int MAX = 100000;
// Variable to represent block size.
// This is made global so compare()
// of sort can use it.
static int block;
// Structure to represent a query range
static class Query
{
// Starting index
int L;
// Ending index
int R;
// Index of query
int index;
// Count of even
// even digit sum
int even;
public Query(int l, int r,
int index, int even)
{
this.L = l;
this.R = r;
this.index = index;
this.even = even;
}
};
// To store the count of
// even digit sum
static int count_even;
// Function to find the digit sum
// for a number
static int digitSum(int num)
{
int sum = 0;
while (num > 0)
{
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to Add elements
// of current range
static void add(int currL, int a[])
{
// If digit sum of a[currL]
// is even then increment
if (digitSum(a[currL]) % 2 == 0)
count_even++;
}
// Function to remove elements
// of previous range
static void remove(int currR, int a[])
{
// If digit sum of a[currL]
// is even then decrement
if (digitSum(a[currR]) % 2 == 0)
count_even--;
}
// Function to generate
// the result of queries
static void queryResults(int a[], int n,
Query q[], int m)
{
// Initialize number of
// even digit sum to 0
count_even = 0;
// Find block size
block = (int) Math.sqrt(n);
// Sort all queries so that queries of
// same blocks are arranged together.
Collections.sort(Arrays.asList(q),
new Comparator<Query>()
{
// Function used to sort all queries so that
// all queries of the same block are arranged
// together and within a block, queries are
// sorted in increasing order of R values.
public int compare(Query x, Query y)
{
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block - y.L / block;
// Same block, sort by R value
return x.R - y.R;
}
});
// Initialize current L, current R and
// current result
int currL = 0, currR = 0;
for(int i = 0; i < m; i++)
{
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Add Elements of current range
while (currR <= R)
{
add(currR, a);
currR++;
}
while (currL > L)
{
add(currL - 1, a);
currL--;
}
// Remove element of previous range
while (currR > R + 1)
{
remove(currR - 1, a);
currR--;
}
while (currL < L)
{
remove(currL, a);
currL++;
}
q[i].even = count_even;
}
}
// Function to display the results of
// queries in their initial order
static void printResults(Query q[], int m)
{
Collections.sort(Arrays.asList(q),
new Comparator<Query>()
{
// Function used to sort all queries
// in order of their index value so that
// results of queries can be printed
// in same order as of input
public int compare(Query x, Query y)
{
return x.index - y.index;
}
});
for(int i = 0; i < m; i++)
{
System.out.println(q[i].even);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 2, 3, 1, 4, 8, 10, 12 };
int n = arr.length;
Query q[] = { new Query(1, 3, 0, 0),
new Query(0, 4, 1, 0),
new Query(4, 7, 2, 0) };
int m = q.length;
queryResults(arr, n, q, m);
printResults(q, m);
}
}
// This code is contributed by sanjeev2552
Python3
# Python program to count of even # digit sum elements in the given # range using MO's algorithm import math import functools MAX = 100000 arr = [5, 2, 3, 1, 4, 8, 10, 12] n = len(arr) # Variable to represent block size. # This is made here so compare() # of sort can use it. block = int(math.sqrt(n)) # Class to represent a query range class Query: def __init__(self, l, r, index, even): self.L = l # Starting index self.R = r # Ending index self.index = index # Index of query self.even = even # Count of even digit sum # Function used to sort all queries so that # all queries of the same block are arranged # together and within a block, queries are # sorted in increasing order of R values. def compare(x, y): # Different blocks, sort by block. if x.L / block != y.L / block: return x.L / block < y.L / block else: # Same block, sort by R value return x.R < y.R # Function to find the digit sum # for a number def digitSum(num): sum = 0 while num > 0: sum += (num % 10) num //= 10 return sum # Function to Add elements # of current range def add(currL, a, count_even): # If digit sum of a[currL] # is even then increment if digitSum(a[currL]) % 2 == 0: count_even += 1 return count_even # Function to remove elements # of previous range def remove(currR, a, count_even): # If digit sum of a[currL] # is even then decrement if digitSum(a[currR]) % 2 == 0: count_even -= 1 return count_even # Function to generate # the result of queries def queryResults(a, n, q, m): # Initialize number of # even digit sum to 0 count_even = 0 # Find block size block = int(math.sqrt(n)) # Sort all queries so that queries of # same blocks are arranged together. q.sort(key=functools.cmp_to_key(compare)) # Initialize current L, current R and # current result currL = 0 currR = 0 for i in range(m): # L and R values of current range L = q[i].L R = q[i].R # Add Elements of current range while currR <= R: count_even = add(currR, a, count_even) currR += 1 while currL > L: count_even = add(currL - 1, a, count_even) currL -= 1 # Remove element of previous range while currR > R + 1: count_even = remove(currR - 1, a, count_even) currR -= 1 while currL < L: count_even = remove(currL, a, count_even) currL += 1 q[i].even = count_even # Function to display the results of # queries in their initial order def printResults(q, m): q.sort(key=lambda x: x.index) for i in range(m): print(q[i].even) # Driver Code q = [Query(1, 3, 0, 0), Query(0, 4, 1, 0), Query(4, 7, 2, 0)] m = len(q) queryResults(arr, n, q, m) printResults(q, m) # This code is contributed by Tapesh (tapeshdua420)
Producción:
1 2 2
Complejidad temporal: O(Q x √N)
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA