Dada una array binaria arr[] de tamaño N y una array 2D Q[][] que contiene K consultas de los siguientes dos tipos:
- 1 : Imprime la longitud del subarreglo más largo que consta de solo 1 s.
- 2 X : Voltee el elemento en el índice X ( indexación basada en 1 ), es decir, cambie el elemento a ‘1’ si el elemento actual es ‘0’ y viceversa.
Ejemplos:
Entrada: N = 10, arr[] = {1, 1, 0, 1, 1, 1, 0, 0, 1, 1}, K=3, Q[][] = {{1}, {2, 3}, {1}}
Salida: 3 6
Explicación:
Consulta 1: La longitud del subarreglo más largo de 1 s solo es 3.
Consulta 2: Cambia el carácter ‘0’ en el índice 2 a ‘1’ . Por lo tanto, arr[] se modifica a {1, 1, 1, 1, 1, 1, 0, 0, 1, 1}.
Consulta 3: la longitud del subarreglo más largo de solo 1 s es 6.Entrada: N = 7, arr[] = {1, 1, 1, 1, 1, 1, 0}, K=3, Q[][]={{1}, {2, 7}, {1} }
Salida: 6 7
Explicación:
Consulta 1: La longitud del subarreglo más largo de 1 s solo es 6.
Consulta 2: Voltee el carácter ‘0’ en la posición 7. Por lo tanto, la array arr[] se modifica a {1, 1, 1 , 1, 1, 1, 1}.
Consulta 3: la longitud del subarreglo más largo de solo 1 s es 7.
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array arr[] para cada consulta y realizar las operaciones dadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the longest subarray
// consisting of 1s only
int longestsubarray(int a[], int N)
{
// Stores the maximum length of
// subarray containing 1s only
int maxlength = 0, sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If current element is '1'
if (a[i] == 1) {
// Increment length
sum++;
}
// Otherwise
else {
// Reset length
sum = 0;
}
// Update maximum subarray length
maxlength = max(maxlength, sum);
}
return maxlength;
}
// Function to perform given queries
void solveQueries(int arr[], int n,
vector<vector<int> > Q, int k)
{
// Stores count of queries
int cntQuery = Q.size();
// Traverse each query
for (int i = 0; i < cntQuery; i++) {
if (Q[i][0] == 1) {
cout << longestsubarray(arr, n) << " ";
}
else {
// Flip the character
arr[Q[i][1] - 1] ^= 1;
}
}
}
// Driver Code
int main()
{
// Size of array
int N = 10;
// Given array
int arr[] = { 1, 1, 0, 1, 1,
1, 0, 0, 1, 1 };
// Given queries
vector<vector<int> > Q = { { 1 }, { 2, 3 }, { 1 } };
// Number of queries
int K = 3;
solveQueries(arr, N, Q, K);
}
Java
// Java Program for the above approach
import java.util.*;
public class Main
{
// Function to calculate the longest subarray
// consisting of 1s only
static int longestsubarray(int a[], int N)
{
// Stores the maximum length of
// subarray containing 1s only
int maxlength = 0, sum = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// If current element is '1'
if (a[i] == 1)
{
// Increment length
sum++;
}
// Otherwise
else
{
// Reset length
sum = 0;
}
// Update maximum subarray length
maxlength = Math.max(maxlength, sum);
}
return maxlength;
}
// Function to perform given queries
static void solveQueries(int arr[], int n,
Vector<Vector<Integer>> Q, int k)
{
// Stores count of queries
int cntQuery = Q.size();
// Traverse each query
for (int i = 0; i < cntQuery; i++)
{
if (Q.get(i).get(0) == 1)
{
System.out.print(longestsubarray(arr, n) + " ");
}
else
{
// Flip the character
arr[Q.get(i).get(1) - 1] ^= 1;
}
}
}
public static void main(String[] args) {
// Size of array
int N = 10;
// Given array
int arr[] = { 1, 1, 0, 1, 1,
1, 0, 0, 1, 1 };
// Given queries
Vector<Vector<Integer>> Q = new Vector<Vector<Integer>>();
Vector<Integer> v1 = new Vector<Integer>();
Vector<Integer> v2 = new Vector<Integer>();
Vector<Integer> v3 = new Vector<Integer>();
v1.add(1);
v2.add(2);
v2.add(3);
v3.add(1);
Q.add(v1);
Q.add(v2);
Q.add(v3);
// Number of queries
int K = 3;
solveQueries(arr, N, Q, K);
}
}
// This code is contributed by divyesh072019
Python3
# Python Program for the above approach # Function to calculate the longest subarray # consisting of 1s only def longestsubarray(a, N) : # Stores the maximum length of # subarray containing 1s only maxlength = 0 sum = 0 # Traverse the array for i in range(N): # If current element is '1' if (a[i] == 1) : # Increment length sum += 1 # Otherwise else : # Reset length sum = 0 # Update maximum subarray length maxlength = max(maxlength, sum) return maxlength # Function to perform given queries def solveQueries(arr, n, Q, k) : # Stores count of queries cntQuery = len(Q) # Traverse each query for i in range(cntQuery): if (Q[i][0] == 1) : print(longestsubarray(arr, n), end = " ") else : # Flip the character arr[Q[i][1] - 1] ^= 1 # Driver Code # Size of array N = 10 # Given array arr = [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1] # Given queries Q = [[1], [ 2, 3 ], [1]] # Number of queries K = 3 solveQueries(arr, N, Q, K) # This code is contributed by sanjoy_62
C#
// C# Program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate the longest subarray
// consisting of 1s only
static int longestsubarray(int[] a, int N)
{
// Stores the maximum length of
// subarray containing 1s only
int maxlength = 0, sum = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// If current element is '1'
if (a[i] == 1)
{
// Increment length
sum++;
}
// Otherwise
else
{
// Reset length
sum = 0;
}
// Update maximum subarray length
maxlength = Math.Max(maxlength, sum);
}
return maxlength;
}
// Function to perform given queries
static void solveQueries(int[] arr, int n,
List<List<int>> Q, int k)
{
// Stores count of queries
int cntQuery = Q.Count;
// Traverse each query
for (int i = 0; i < cntQuery; i++)
{
if (Q[i][0] == 1)
{
Console.Write(longestsubarray(arr, n) + " ");
}
else
{
// Flip the character
arr[Q[i][1] - 1] ^= 1;
}
}
}
// Driver code
static void Main()
{
// Size of array
int N = 10;
// Given array
int[] arr = { 1, 1, 0, 1, 1,
1, 0, 0, 1, 1 };
// Given queries
List<List<int>> Q = new List<List<int>>();
Q.Add(new List<int> { 1 });
Q.Add(new List<int> { 2, 3 });
Q.Add(new List<int> { 1 });
// Number of queries
int K = 3;
solveQueries(arr, N, Q, K);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript Program for the above approach
// Function to calculate the longest subarray
// consisting of 1s only
function longestsubarray(a, N)
{
// Stores the maximum length of
// subarray containing 1s only
var maxlength = 0, sum = 0;
// Traverse the array
for (var i = 0; i < N; i++) {
// If current element is '1'
if (a[i] == 1) {
// Increment length
sum++;
}
// Otherwise
else {
// Reset length
sum = 0;
}
// Update maximum subarray length
maxlength = Math.max(maxlength, sum);
}
return maxlength;
}
// Function to perform given queries
function solveQueries(arr, n, Q, k)
{
// Stores count of queries
var cntQuery = Q.length;
// Traverse each query
for (var i = 0; i < cntQuery; i++) {
if (Q[i][0] == 1) {
document.write( longestsubarray(arr, n) + " ");
}
else {
// Flip the character
arr[Q[i][1] - 1] ^= 1;
}
}
}
// Driver Code
// Size of array
var N = 10;
// Given array
var arr = [1, 1, 0, 1, 1,
1, 0, 0, 1, 1 ];
// Given queries
var Q = [ [ 1 ], [ 2, 3 ], [ 1 ] ];
// Number of queries
var K = 3;
solveQueries(arr, N, Q, K);
</script>
Producción:
3 6
Complejidad de Tiempo: (N * K)
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la estructura de datos del árbol de segmentos . El problema planteado se puede resolver con base en las siguientes observaciones:
- Se puede observar fácilmente que se necesitan al menos tres cosas para fusionar dos Nodes de un árbol de segmentos . Por lo tanto, se requieren árboles de 3 segmentos, digamos MAX[], pref[] y suf[] . MAX[]: almacena la longitud del subarreglo más largo que consiste solo en 1 s, pre[] y suf[] almacenarán la longitud más larga de prefijo y sufijo respectivamente.
- La fusión de dos Nodes se puede hacer usando lo siguiente:
- MAX[i] = max(MAX[2*i], max(MAX[2*i + 1], suf[2*v + 1] + pref[2*i]))
- preferencia[v] = max(preferencia[v * 2], preferencia[2 * v] + (preferencia[2 * v] == tm – tl + 1) * preferencia[v * 2 + 1])
- suf[v] = max(suf[v * 2 + 1], suf[2 * v + 1] + suf[v * 2] * (suf[2 * v + 1] == tr – tm))
- Aquí i, 2*i, 2*i + 1 son el Node actual, el hijo izquierdo y el hijo derecho respectivamente, y tl, tr es el rango actual
Siga los pasos a continuación para resolver el problema:
- Para la consulta de tipo 1, imprima el Node raíz, MAX[1] del árbol de segmentos que contiene la longitud más larga del subarreglo que consta de solo 1 solo en el rango [1, N]
- Para la consulta de tipo 2, invierta la posición dada y actualice el árbol de segmentos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000
// Arrays to store prefix sums, suffix
// and MAX's node respectively
int pref[500005];
int suf[500005];
int MAX[500005];
// Function to construct Segment Tree
void build(int a[], int tl, int tr, int v)
{
if (tl == tr) {
// MAX array for node MAX
MAX[v] = a[tl];
// Array for prefix sum node
pref[v] = a[tl];
// Array for suffix sum node
suf[v] = a[tl];
}
else {
int tm = (tl + tr) / 2;
build(a, tl, tm, v * 2);
build(a, tm + 1, tr, v * 2 + 1);
// Calculate MAX node
MAX[v] = max(MAX[v * 2],
max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
pref[v] = max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == tm - tl + 1)
* pref[v * 2 + 1]);
suf[v] = max(
suf[v * 2 + 1],
suf[2 * v + 1]
+ suf[v * 2] * (suf[2 * v + 1] == tr - tm));
}
}
// Function to update Segment Tree
void update(int a[], int pos, int tl,
int tr, int v)
{
if (tl > pos || tr < pos) {
return;
}
// Update at position
if (tl == tr && tl == pos) {
MAX[v] = a[pos];
pref[v] = a[pos];
suf[v] = a[pos];
}
else {
// Update sums from bottom to the
// top of Segment Tree
int tm = (tl + tr) / 2;
update(a, pos, tl, tm, v * 2);
update(a, pos, tm + 1, tr, v * 2 + 1);
// Update MAX tree
MAX[v] = max(MAX[v * 2],
max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
// Update pref tree
pref[v] = max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == tm - tl + 1)
* pref[v * 2 + 1]);
// Update suf tree
suf[v] = max(suf[v * 2 + 1],
suf[2 * v + 1]
+ (suf[2 * v + 1] == tr - tm)
* suf[v * 2]);
}
}
// Function to perform given queries
void solveQueries(int arr[], int n,
vector<vector<int> > Q, int k)
{
// Stores count of queries
int cntQuery = Q.size();
build(arr, 0, n - 1, 1);
// Traverse each query
for (int i = 0; i < cntQuery; i++) {
if (Q[i][0] == 1) {
// Print longest length of subarray in [1, N]
cout << MAX[1] << " ";
}
else {
// Flip the character
arr[Q[i][1] - 1] ^= 1;
update(arr, Q[i][1] - 1, 0, n - 1, 1);
}
}
}
// Driver Code
int main()
{
// Size of array
int N = 10;
// Given array
int arr[] = { 1, 1, 0, 1, 1,
1, 0, 0, 1, 1 };
// Given queries
vector<vector<int> > Q = { { 1 }, { 2, 3 }, { 1 } };
// Number of queries
int K = 3;
solveQueries(arr, N, Q, K);
}
Java
// Java Program for the above approach
import java.util.*;
class GFG
{
static final int INF = 1000000;
// Arrays to store prefix sums, suffix
// and MAX's node respectively
static int []pref = new int[500005];
static int []suf = new int[500005];
static int []MAX = new int[500005];
// Function to construct Segment Tree
static void build(int a[], int tl, int tr, int v)
{
if (tl == tr) {
// MAX array for node MAX
MAX[v] = a[tl];
// Array for prefix sum node
pref[v] = a[tl];
// Array for suffix sum node
suf[v] = a[tl];
}
else {
int tm = (tl + tr) / 2;
build(a, tl, tm, v * 2);
build(a, tm + 1, tr, v * 2 + 1);
// Calculate MAX node
MAX[v] = Math.max(MAX[v * 2],
Math.max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
pref[v] = Math.max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == (tm - tl + 1)?1:0)
* pref[v * 2 + 1]);
suf[v] = Math.max(
suf[v * 2 + 1],
suf[2 * v + 1]
+ suf[v * 2] * (suf[2 * v + 1] == (tr - tm)?1:0));
}
}
// Function to update Segment Tree
static void update(int a[], int pos, int tl,
int tr, int v)
{
if (tl > pos || tr < pos) {
return;
}
// Update at position
if (tl == tr && tl == pos)
{
MAX[v] = a[pos];
pref[v] = a[pos];
suf[v] = a[pos];
}
else {
// Update sums from bottom to the
// top of Segment Tree
int tm = (tl + tr) / 2;
update(a, pos, tl, tm, v * 2);
update(a, pos, tm + 1, tr, v * 2 + 1);
// Update MAX tree
MAX[v] = Math.max(MAX[v * 2],
Math.max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
// Update pref tree
pref[v] = Math.max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == (tm - tl + 1)?1:0)
* pref[v * 2 + 1]);
// Update suf tree
suf[v] = Math.max(suf[v * 2 + 1],
suf[2 * v + 1]
+ (suf[2 * v + 1] == (tr - tm)?1:0)
* suf[v * 2]);
}
}
// Function to perform given queries
static void solveQueries(int arr[], int n,
int[][] Q, int k)
{
// Stores count of queries
int cntQuery = Q.length;
build(arr, 0, n - 1, 1);
// Traverse each query
for (int i = 0; i < cntQuery; i++)
{
if (Q[i][0] == 1)
{
// Print longest length of subarray in [1, N]
System.out.print(MAX[1]+ " ");
}
else
{
// Flip the character
arr[Q[i][1] - 1] ^= 1;
update(arr, Q[i][1] - 1, 0, n - 1, 1);
}
}
}
// Driver Code
public static void main(String[] args)
{
// Size of array
int N = 10;
// Given array
int arr[] = { 1, 1, 0, 1, 1,
1, 0, 0, 1, 1 };
// Given queries
int [][]Q = { { 1 }, { 2, 3 }, { 1 } };
// Number of queries
int K = 3;
solveQueries(arr, N, Q, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 Program for the above approach INF = 1000000 # Arrays to store prefix sums, suffix # and MAX's node respectively pref = [0 for i in range(500005)] suf = [0 for i in range(500005)] MAX = [0 for i in range(500005)] # Function to construct Segment Tree def build(a, tl,tr,v): global MAX global pref global suf if (tl == tr): # MAX array for node MAX MAX[v] = a[tl] # Array for prefix sum node pref[v] = a[tl] # Array for suffix sum node suf[v] = a[tl] else: tm = (tl + tr) // 2 build(a, tl, tm, v * 2) build(a, tm + 1, tr, v * 2 + 1) # Calculate MAX node MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])) pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1)* pref[v * 2 + 1]) suf[v] = max(suf[v * 2 + 1],suf[2 * v + 1]+suf[v * 2] * (suf[2 * v + 1] == tr - tm)) # Function to update Segment Tree def update(a,pos,tl,tr,v): global pref global suf global MAX if (tl > pos or tr < pos): return # Update at position if (tl == tr and tl == pos): MAX[v] = a[pos] pref[v] = a[pos] suf[v] = a[pos] else: # Update sums from bottom to the # top of Segment Tree tm = (tl + tr) // 2 update(a, pos, tl, tm, v * 2) update(a, pos, tm + 1, tr, v * 2 + 1) # Update MAX tree MAX[v] = max(MAX[v * 2], max(MAX[v * 2 + 1], suf[v * 2] + pref[v * 2 + 1])) # Update pref tree pref[v] = max(pref[v * 2], pref[2 * v] + (pref[2 * v] == tm - tl + 1) * pref[v * 2 + 1]) # Update suf tree suf[v] = max(suf[v * 2 + 1], suf[2 * v + 1] + (suf[2 * v + 1] == tr - tm) * suf[v * 2]) # Function to perform given queries def solveQueries(arr, n, Q, k): global MAX # Stores count of queries cntQuery = len(Q) build(arr, 0, n - 1, 1) # Traverse each query for i in range(cntQuery): if (Q[i][0] == 1): # Print longest length of subarray in [1, N] print(MAX[1],end = " ") else: # Flip the character arr[Q[i][1] - 1] ^= 1 update(arr, Q[i][1] - 1, 0, n - 1, 1) # Driver Code if __name__ == '__main__': # Size of array N = 10 # Given array arr = [1, 1, 0, 1, 1, 1, 0, 0, 1, 1] # Given queries Q = [[1], [2, 3], [1]] # Number of queries K = 3 solveQueries(arr, N, Q, K) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# Program for the above approach
using System;
class GFG
{
static readonly int INF = 1000000;
// Arrays to store prefix sums, suffix
// and MAX's node respectively
static int []pref = new int[500005];
static int []suf = new int[500005];
static int []MAX = new int[500005];
// Function to construct Segment Tree
static void build(int []a, int tl, int tr, int v)
{
if (tl == tr)
{
// MAX array for node MAX
MAX[v] = a[tl];
// Array for prefix sum node
pref[v] = a[tl];
// Array for suffix sum node
suf[v] = a[tl];
}
else
{
int tm = (tl + tr) / 2;
build(a, tl, tm, v * 2);
build(a, tm + 1, tr, v * 2 + 1);
// Calculate MAX node
MAX[v] = Math.Max(MAX[v * 2],
Math.Max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
pref[v] = Math.Max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == (tm - tl + 1)?1:0)
* pref[v * 2 + 1]);
suf[v] = Math.Max(
suf[v * 2 + 1],
suf[2 * v + 1]
+ suf[v * 2] * (suf[2 * v + 1] == (tr - tm)?1:0));
}
}
// Function to update Segment Tree
static void update(int []a, int pos, int tl,
int tr, int v)
{
if (tl > pos || tr < pos)
{
return;
}
// Update at position
if (tl == tr && tl == pos)
{
MAX[v] = a[pos];
pref[v] = a[pos];
suf[v] = a[pos];
}
else
{
// Update sums from bottom to the
// top of Segment Tree
int tm = (tl + tr) / 2;
update(a, pos, tl, tm, v * 2);
update(a, pos, tm + 1, tr, v * 2 + 1);
// Update MAX tree
MAX[v] = Math.Max(MAX[v * 2],
Math.Max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
// Update pref tree
pref[v] = Math.Max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == (tm - tl + 1)?1:0)
* pref[v * 2 + 1]);
// Update suf tree
suf[v] = Math.Max(suf[v * 2 + 1],
suf[2 * v + 1]
+ (suf[2 * v + 1] == (tr - tm)?1:0)
* suf[v * 2]);
}
}
// Function to perform given queries
static void solveQueries(int []arr, int n,
int[,] Q, int k)
{
// Stores count of queries
int cntQuery = Q.GetLength(0);
build(arr, 0, n - 1, 1);
// Traverse each query
for (int i = 0; i < cntQuery; i++)
{
if (Q[i, 0] == 1)
{
// Print longest length of subarray in [1, N]
Console.Write(MAX[1] + " ");
}
else
{
// Flip the character
arr[Q[i, 1] - 1] ^= 1;
update(arr, Q[i, 1] - 1, 0, n - 1, 1);
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Size of array
int N = 10;
// Given array
int []arr = { 1, 1, 0, 1, 1,
1, 0, 0, 1, 1 };
// Given queries
int [,]Q = { { 1,0 }, { 2, 3 }, { 1,0 } };
// Number of queries
int K = 3;
solveQueries(arr, N, Q, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program for the above approach
let INF = 1000000
// Arrays to store prefix sums, suffix
// and MAX's node respectively
let pref = new Array(500005);
let suf = new Array(500005);
let MAX = new Array(500005);
// Function to construct Segment Tree
function build(a, tl, tr, v)
{
if (tl == tr) {
// MAX array for node MAX
MAX[v] = a[tl];
// Array for prefix sum node
pref[v] = a[tl];
// Array for suffix sum node
suf[v] = a[tl];
}
else {
let tm = Math.floor((tl + tr) / 2);
build(a, tl, tm, v * 2);
build(a, tm + 1, tr, v * 2 + 1);
// Calculate MAX node
MAX[v] = Math.max(MAX[v * 2],
Math.max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
pref[v] = Math.max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == tm - tl + 1)
* pref[v * 2 + 1]);
suf[v] = Math.max(
suf[v * 2 + 1],
suf[2 * v + 1]
+ suf[v * 2] * (suf[2 * v + 1] == tr - tm));
}
}
// Function to update Segment Tree
function update(a, pos, tl,tr, v)
{
if (tl > pos || tr < pos) {
return;
}
// Update at position
if (tl == tr && tl == pos) {
MAX[v] = a[pos];
pref[v] = a[pos];
suf[v] = a[pos];
}
else {
// Update sums from bottom to the
// top of Segment Tree
let tm = Math.floor((tl + tr) / 2);
update(a, pos, tl, tm, v * 2);
update(a, pos, tm + 1, tr, v * 2 + 1);
// Update MAX tree
MAX[v] = Math.max(MAX[v * 2],
Math.max(MAX[v * 2 + 1],
suf[v * 2] + pref[v * 2 + 1]));
// Update pref tree
pref[v] = Math.max(pref[v * 2],
pref[2 * v]
+ (pref[2 * v] == tm - tl + 1)
* pref[v * 2 + 1]);
// Update suf tree
suf[v] = Math.max(suf[v * 2 + 1],
suf[2 * v + 1]
+ (suf[2 * v + 1] == tr - tm)
* suf[v * 2]);
}
}
// Function to perform given queries
function solveQueries(arr, n, Q, k)
{
// Stores count of queries
let cntQuery = Q.length;
build(arr, 0, n - 1, 1);
// Traverse each query
for (let i = 0; i < cntQuery; i++) {
if (Q[i][0] == 1) {
// Print longest length of subarray in [1, N]
document.write(MAX[1] + " ");
}
else {
// Flip the character
arr[Q[i][1] - 1] ^= 1;
update(arr, Q[i][1] - 1, 0, n - 1, 1);
}
}
}
// Driver Code
// Size of array
let N = 10;
// Given array
let arr = [ 1, 1, 0, 1, 1, 1, 0, 0, 1, 1 ];
// Given queries
let Q = [ [ 1 ], [ 2, 3 ], [ 1 ] ];
// Number of queries
let K = 3;
solveQueries(arr, N, Q, K);
// This code is contributed by shinjanpatra
</script>
Producción:
3 6
Complejidad de tiempo: O(max(K*log(N), N*log(N)))
Espacio auxiliar: O(4*N)
Publicación traducida automáticamente
Artículo escrito por aaryaverma112 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA