Givenarray arr[] de tamaño N que contiene variables cíclicas que tienen estados de 0 a ( M – 1) (es decir, cuando se incrementa de M-1 va a 0 ). La tarea es cumplir con las consultas Q que sean de cualquiera de los dos tipos siguientes:
- 1er tipo: 1 LRK: incrementa todos los valores en el rango de índices [L, R], K veces cíclicamente.
- 2do tipo: 2 LR: imprime los valores actualizados en el rango de índices [L, R].
Ejemplos:
Entrada: arr[] = {2, 2, 7, 2, 5}, Q = 5, M = 8
consultas[][] = {{1, 0, 3, 4},
{1, 4, 4, 2 },
{1, 0, 0, 7},
{2, 1, 3},
{2, 3, 3}}
Salida: {6, 3, 6}, {6}
Explicación: Los estados después de realizar cada operación son :
Después del 1.º: {6, 6, 3, 6, 5}
Después del 2.º: {6, 6, 3, 6, 7}
Después del 3.º: {5, 6, 3, 6, 7}
Entonces, en el cuarto elemento de consulta del índice 1 a 3 y en el 5º elemento de consulta en el índice 3 se imprimen.Entrada: arr[] = [2, 3, 4, 5], Q = 3, M = 6
consultas[][] = {{1, 0, 0, 3},
{1, 1, 2, 2},
{1, 3, 3, 1},
{2, 0, 3}}
Salida: {5, 5, 1, 1}
Enfoque: el problema se puede resolver utilizando un enfoque codicioso. Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Cuando una consulta es de primer tipo, actualice todos los valores en el rango [L, R], K veces.
- Cuando una consulta es de segundo tipo, imprima el valor en el rango [L, R].
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to implement the queries
void update(int arr[], int N, int M, int Q,
vector<vector<int> >& queries)
{
// Loop to implement the queries
for (int i = 0; i < Q; i++) {
if (queries[i][0] == 1) {
for (int j = queries[i][1];
j <= queries[i][2];
j++)
arr[j] = (arr[j] +
queries[i][3]) % M;
}
else if (queries[i][0] == 2) {
for (int j = queries[i][1];
j <= queries[i][2];
j++)
cout << arr[j] << " ";
cout << endl;
}
}
}
// Driver's code
int main()
{
int N = 5, M = 8, Q = 5;
int arr[] = { 2, 2, 7, 2, 5 };
vector<vector<int> > queries(Q);
queries[0] = { 1, 0, 3, 4 };
queries[1] = { 1, 4, 4, 2 };
queries[2] = { 1, 0, 0, 7 };
queries[3] = { 2, 1, 3 };
queries[4] = { 2, 3, 3 };
update(arr, N, M, Q, queries);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
class GFG {
// Function to implement the queries
public static void update(int[] arr, int N, int M,
int Q, int[][] queries)
{
// Loop to implement the queries
for (int i = 0; i < Q; i++) {
if (queries[i][0] == 1) {
for (int j = queries[i][1];
j <= queries[i][2];
j++)
arr[j] = (arr[j] +
queries[i][3]) % M;
}
else if (queries[i][0] == 2) {
for (int j = queries[i][1];
j <= queries[i][2];
j++)
System.out.print(arr[j]+ " ");
System.out.println();
}
}
}
// Driver's code
public static void main (String[] args)
{
int N = 5, M = 8, Q = 5;
int[] arr = { 2, 2, 7, 2, 5 };
int[][] queries = new int[][]
{
new int[] { 1, 0, 3, 4 },
new int[] { 1, 4, 4, 2 },
new int[] { 1, 0, 0, 7 },
new int[] { 2, 1, 3 },
new int[] { 2, 3, 3 }
};
update(arr, N, M, Q, queries);
}
}
// This code is contributed by Shubham Singh
Python3
# Python3 code to implement above approach # Function to implement the queries def update(arr, N, M, Q, queries): # Loop to implement the queries for i in range(Q): if (queries[i][0] == 1): for j in range(queries[i][1], queries[i][2] + 1): arr[j] = (arr[j] + queries[i][3]) % M elif (queries[i][0] == 2): for j in range(queries[i][1], queries[i][2] + 1): print(arr[j], end = " ") print() # Driver code if __name__ == "__main__": N = 5 M = 8 Q = 5 arr = [2, 2, 7, 2, 5] queries = [] queries.append([1, 0, 3, 4]) queries.append([1, 4, 4, 2]) queries.append([1, 0, 0, 7]) queries.append([2, 1, 3]) queries.append([2, 3, 3]) update(arr, N, M, Q, queries) # This code is contributed by ukasp
C#
// C# code to implement the above approach
using System;
public class GFG{
// Function to implement the queries
public static void update(int[] arr, int N, int M, int Q, int[][] queries)
{
// Loop to implement the queries
for (int i = 0; i < Q; i++) {
if (queries[i][0] == 1) {
for (int j = queries[i][1];
j <= queries[i][2];
j++)
arr[j] = (arr[j] +
queries[i][3]) % M;
}
else if (queries[i][0] == 2) {
for (int j = queries[i][1];
j <= queries[i][2];
j++)
Console.Write(arr[j]+ " ");
Console.WriteLine();
}
}
}
// Driver's code
public static void Main()
{
int N = 5, M = 8, Q = 5;
int[] arr = { 2, 2, 7, 2, 5 };
int[][] queries = new int[][]
{
new int[] { 1, 0, 3, 4 },
new int[] { 1, 4, 4, 2 },
new int[] { 1, 0, 0, 7 },
new int[] { 2, 1, 3 },
new int[] { 2, 3, 3 }
};
update(arr, N, M, Q, queries);
}
}
// This code is contributed by Shubham Singh
Javascript
<script>
// JavaScript code for the above approach
// Function to implement the queries
function update(arr, N, M, Q,
queries)
{
// Loop to implement the queries
for (let i = 0; i < Q; i++) {
if (queries[i][0] == 1) {
for (let j = queries[i][1];
j <= queries[i][2];
j++)
arr[j] = (arr[j] +
queries[i][3]) % M;
}
else if (queries[i][0] == 2) {
for (let j = queries[i][1];
j <= queries[i][2];
j++)
document.write(arr[j] + " ");
document.write('<br>')
}
}
}
// Driver's code
let N = 5, M = 8, Q = 5;
let arr = [2, 2, 7, 2, 5];
let queries = new Array(Q);
queries[0] = [1, 0, 3, 4];
queries[1] = [1, 4, 4, 2];
queries[2] = [1, 0, 0, 7];
queries[3] = [2, 1, 3];
queries[4] = [2, 3, 3];
update(arr, N, M, Q, queries);
// This code is contributed by Potta Lokesh
</script>
6 3 6 6
Complejidad temporal: O(Q*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA