Dada una array binaria arr[] de tamaño N . La tarea es responder a las consultas Q que pueden ser de cualquier tipo a continuación:
Tipo 1 – 1 lr : Realiza la operación xor bit a bit en todos los elementos de la array de l a r con 1.
Tipo 2 – 2 lr : Devuelve la distancia mínima entre dos elementos con valor 1 en un subarreglo [l, r].
Tipo 3 – 3 lr : Devuelve la distancia máxima entre dos elementos con valor 1 en un subarreglo [l, r].
Tipo 4 – 4 lr : Devuelve la distancia mínima entre dos elementos con valor 0 en un subarreglo [l, r].
Tipo 5 – 5 lr : Devuelve la distancia máxima entre dos elementos con valor 0 en un subarreglo [l, r].
Ejemplos:
Entrada: arr[] = {1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0}, q=5
Salida: 2 2 3 2
Explicación:
consulta 1: Tipo 2, l=3, r=7
El rango 3 a 7 contiene { 1, 0, 1, 0, 1 }.
Entonces, la distancia mínima entre dos elementos con valor 1 es 2.
consulta 2: Tipo 3, l=2, r=5
El rango 2 a 5 contiene { 0, 1, 0, 1 }.
Entonces, la distancia máxima entre dos elementos con valor 1 es 2.
consulta 3: Tipo 1, l=1, r=4
Después de actualizar, la array se convierte en {1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0}
consulta 4: Tipo 4, l=3, r=7
El rango 3 a 7 en la array actualizada contiene { 0, 1, 1, 0, 1 }.
Entonces, la distancia mínima entre dos elementos con valor 0 es 3.
consulta 5: Tipo 5, l=4, r=9
El rango 4 a 9 contiene { 1, 1, 0, 1, 0, 1 }.
Entonces, la distancia máxima entre dos elementos con valor 0 es 2.
Enfoque:
crearemos un árbol de segmentos y usaremos actualizaciones de rango con propagación diferida para resolver esto.
- Cada Node en el árbol de segmentos tendrá el índice de 1 más a la izquierda y 1 más a la derecha, 0 más a la izquierda y 0 más a la derecha y números enteros que contienen la distancia máxima y mínima entre cualquier elemento con valor 1 en un subarreglo {l, r} también como la distancia máxima y mínima entre cualquier elemento con valor 0 en un subarreglo {l, r}.
- Ahora, en este árbol de segmentos podemos fusionar los Nodes izquierdo y derecho como se muestra a continuación:
CPP
// l1 = leftmost index of 1, l0 = leftmost index of 0.
// r1 = rightmost index of 1, r0 = rightmost index of 0.
// max1 = maximum distance between two 1’s.
// max0 = maximum distance between two 0’s.
// min1 = minimum distance between two 1’s.
// min0 = minimum distance between two 0’s.
node Merge(node left, node right)
{
node cur;
if left.l0 is valid
cur.l0 = left.l0
else
cur.l0 = r.l0
// We will do this for all values
// i.e. cur.r0, cur.l1, cur.r1, cur.l0
// To find the min and max difference between two 1's and 0's
// we will take min/max value of left side, right side and
// difference between rightmost index of 1/0 in right node
// and leftmost index of 1/0 in left node respectively.
cur.min0 = minimum of left.min0 and right.min0
if left.r0 is valid and right.l0 is valid
cur.min0 = minimum of cur.min0 and (right.l0 - left.r0)
// We will do this for all max/min values
// i.e. cur.min0, cur.min1, cur.max1, cur.max0
return cur;
}
- Para manejar la consulta de actualización de rango, usaremos propagación diferida. La consulta de actualización nos pide xor todos los elementos en el rango de l a r con 1, y de las observaciones, sabemos que:
0 xor 1 = 1
1 xor 1 = 0
- Por lo tanto, podemos observar que después de esta actualización, todos los 0 cambiarán a 1 y todos los 1 cambiarán a 0. Por lo tanto, en nuestros Nodes de árbol de segmentos, todos los valores correspondientes para 0 y 1 también se intercambiarán, es decir
l0 and l1 will get swapped
r0 and r1 will get swapped
min0 and min1 will get swapped
max0 and max1 will get swapped
- Luego, finalmente, para encontrar la respuesta a las tareas 2, 3, 4 y 5, solo necesitamos llamar a la función de consulta para el rango dado {l, r} y para encontrar la respuesta a la tarea 1, necesitamos llamar a la función de actualización de rango .
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program for the given problem
#include <bits/stdc++.h>
using namespace std;
int lazy[100001];
// Class for each node
// in the segment tree
class node {
public:
int l1, r1, l0, r0;
int min0, max0, min1, max1;
node()
{
l1 = r1 = l0 = r0 = -1;
max1 = max0 = INT_MIN;
min1 = min0 = INT_MAX;
}
} seg[100001];
// A utility function for
// merging two nodes
node MergeUtil(node l, node r)
{
node x;
x.l0 = (l.l0 != -1) ? l.l0 : r.l0;
x.r0 = (r.r0 != -1) ? r.r0 : l.r0;
x.l1 = (l.l1 != -1) ? l.l1 : r.l1;
x.r1 = (r.r1 != -1) ? r.r1 : l.r1;
x.min0 = min(l.min0, r.min0);
if (l.r0 != -1 && r.l0 != -1)
x.min0 = min(x.min0, r.l0 - l.r0);
x.min1 = min(l.min1, r.min1);
if (l.r1 != -1 && r.l1 != -1)
x.min1 = min(x.min1, r.l1 - l.r1);
x.max0 = max(l.max0, r.max0);
if (l.l0 != -1 && r.r0 != -1)
x.max0 = max(x.max0, r.r0 - l.l0);
x.max1 = max(l.max1, r.max1);
if (l.l1 != -1 && r.r1 != -1)
x.max1 = max(x.max1, r.r1 - l.l1);
return x;
}
// utility function
// for updating a node
node UpdateUtil(node x)
{
swap(x.l0, x.l1);
swap(x.r0, x.r1);
swap(x.min1, x.min0);
swap(x.max0, x.max1);
return x;
}
// A recursive function that constructs
// Segment Tree for given string
void Build(int qs, int qe, int ind, int arr[])
{
// If start is equal to end then
// insert the array element
if (qs == qe) {
if (arr[qs] == 1) {
seg[ind].l1 = seg[ind].r1 = qs;
}
else {
seg[ind].l0 = seg[ind].r0 = qs;
}
lazy[ind] = 0;
return;
}
int mid = (qs + qe) >> 1;
// Build the segment tree
// for range qs to mid
Build(qs, mid, ind << 1, arr);
// Build the segment tree
// for range mid+1 to qe
Build(mid + 1, qe, ind << 1 | 1, arr);
// merge the two child nodes
// to obtain the parent node
seg[ind] = MergeUtil(
seg[ind << 1],
seg[ind << 1 | 1]);
}
// Query in a range qs to qe
node Query(int qs, int qe,
int ns, int ne, int ind)
{
if (lazy[ind] != 0) {
seg[ind] = UpdateUtil(seg[ind]);
if (ns != ne) {
lazy[ind * 2] ^= lazy[ind];
lazy[ind * 2 + 1] ^= lazy[ind];
}
lazy[ind] = 0;
}
node x;
// If the range lies in this segment
if (qs <= ns && qe >= ne)
return seg[ind];
// If the range is out of the bounds
// of this segment
if (ne < qs || ns > qe || ns > ne)
return x;
// Else query for the right and left
// child node of this subtree
// and merge them
int mid = (ns + ne) >> 1;
node l = Query(qs, qe, ns,
mid, ind << 1);
node r = Query(qs, qe,
mid + 1, ne,
ind << 1 | 1);
x = MergeUtil(l, r);
return x;
}
// range update using lazy propagation
void RangeUpdate(int us, int ue,
int ns, int ne, int ind)
{
if (lazy[ind] != 0) {
seg[ind] = UpdateUtil(seg[ind]);
if (ns != ne) {
lazy[ind * 2] ^= lazy[ind];
lazy[ind * 2 + 1] ^= lazy[ind];
}
lazy[ind] = 0;
}
// If the range is out of the bounds
// of this segment
if (ns > ne || ns > ue || ne < us)
return;
// If the range lies in this segment
if (ns >= us && ne <= ue) {
seg[ind] = UpdateUtil(seg[ind]);
if (ns != ne) {
lazy[ind * 2] ^= 1;
lazy[ind * 2 + 1] ^= 1;
}
return;
}
// Else query for the right and left
// child node of this subtree
// and merge them
int mid = (ns + ne) >> 1;
RangeUpdate(us, ue, ns, mid, ind << 1);
RangeUpdate(us, ue, mid + 1, ne, ind << 1 | 1);
node l = seg[ind << 1], r = seg[ind << 1 | 1];
seg[ind] = MergeUtil(l, r);
}
// Driver code
int main()
{
int arr[] = { 1, 1, 0,
1, 0, 1,
0, 1, 0,
1, 0, 1,
1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
// Build the segment tree
Build(0, n - 1, 1, arr);
// Query of Type 2 in the range 3 to 7
node ans = Query(3, 7, 0, n - 1, 1);
cout << ans.min1 << "\n";
// Query of Type 3 in the range 2 to 5
ans = Query(2, 5, 0, n - 1, 1);
cout << ans.max1 << "\n";
// Query of Type 1 in the range 1 to 4
RangeUpdate(1, 4, 0, n - 1, 1);
// Query of Type 4 in the range 3 to 7
ans = Query(3, 7, 0, n - 1, 1);
cout << ans.min0 << "\n";
// Query of Type 5 in the range 4 to 9
ans = Query(4, 9, 0, n - 1, 1);
cout << ans.max0 << "\n";
return 0;
}
Python3
# Python program for the given problem from sys import maxsize from typing import List INT_MAX = maxsize INT_MIN = -maxsize lazy = [0 for _ in range(100001)] # Class for each node # in the segment tree class node: def __init__(self) -> None: self.l1 = self.r1 = self.l0 = self.r0 = -1 self.max0 = self.max1 = INT_MIN self.min0 = self.min1 = INT_MAX seg = [node() for _ in range(100001)] # A utility function for # merging two nodes def MergeUtil(l: node, r: node) -> node: x = node() x.l0 = l.l0 if (l.l0 != -1) else r.l0 x.r0 = r.r0 if (r.r0 != -1) else l.r0 x.l1 = l.l1 if (l.l1 != -1) else r.l1 x.r1 = r.r1 if (r.r1 != -1) else l.r1 x.min0 = min(l.min0, r.min0) if (l.r0 != -1 and r.l0 != -1): x.min0 = min(x.min0, r.l0 - l.r0) x.min1 = min(l.min1, r.min1) if (l.r1 != -1 and r.l1 != -1): x.min1 = min(x.min1, r.l1 - l.r1) x.max0 = max(l.max0, r.max0) if (l.l0 != -1 and r.r0 != -1): x.max0 = max(x.max0, r.r0 - l.l0) x.max1 = max(l.max1, r.max1) if (l.l1 != -1 and r.r1 != -1): x.max1 = max(x.max1, r.r1 - l.l1) return x # utility function # for updating a node def UpdateUtil(x: node) -> node: x.l0, x.l1 = x.l1, x.l0 x.r0, x.r1 = x.r1, x.r0 x.min1, x.min0 = x.min0, x.min1 x.max0, x.max1 = x.max1, x.max0 return x # A recursive function that constructs # Segment Tree for given string def Build(qs: int, qe: int, ind: int, arr: List[int]) -> None: # If start is equal to end then # insert the array element if (qs == qe): if (arr[qs] == 1): seg[ind].l1 = seg[ind].r1 = qs else: seg[ind].l0 = seg[ind].r0 = qs lazy[ind] = 0 return mid = (qs + qe) >> 1 # Build the segment tree # for range qs to mid Build(qs, mid, ind << 1, arr) # Build the segment tree # for range mid+1 to qe Build(mid + 1, qe, ind << 1 | 1, arr) # merge the two child nodes # to obtain the parent node seg[ind] = MergeUtil(seg[ind << 1], seg[ind << 1 | 1]) # Query in a range qs to qe def Query(qs: int, qe: int, ns: int, ne: int, ind: int) -> node: if (lazy[ind] != 0): seg[ind] = UpdateUtil(seg[ind]) if (ns != ne): lazy[ind * 2] ^= lazy[ind] lazy[ind * 2 + 1] ^= lazy[ind] lazy[ind] = 0 x = node() # If the range lies in this segment if (qs <= ns and qe >= ne): return seg[ind] # If the range is out of the bounds # of this segment if (ne < qs or ns > qe or ns > ne): return x # Else query for the right and left # child node of this subtree # and merge them mid = (ns + ne) >> 1 l = Query(qs, qe, ns, mid, ind << 1) r = Query(qs, qe, mid + 1, ne, ind << 1 | 1) x = MergeUtil(l, r) return x # range update using lazy propagation def RangeUpdate(us: int, ue: int, ns: int, ne: int, ind: int) -> None: if (lazy[ind] != 0): seg[ind] = UpdateUtil(seg[ind]) if (ns != ne): lazy[ind * 2] ^= lazy[ind] lazy[ind * 2 + 1] ^= lazy[ind] lazy[ind] = 0 # If the range is out of the bounds # of this segment if (ns > ne or ns > ue or ne < us): return # If the range lies in this segment if (ns >= us and ne <= ue): seg[ind] = UpdateUtil(seg[ind]) if (ns != ne): lazy[ind * 2] ^= 1 lazy[ind * 2 + 1] ^= 1 return # Else query for the right and left # child node of this subtree # and merge them mid = (ns + ne) >> 1 RangeUpdate(us, ue, ns, mid, ind << 1) RangeUpdate(us, ue, mid + 1, ne, ind << 1 | 1) l = seg[ind << 1] r = seg[ind << 1 | 1] seg[ind] = MergeUtil(l, r) # Driver code if __name__ == "__main__": arr = [1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0] n = len(arr) # Build the segment tree Build(0, n - 1, 1, arr) # Query of Type 2 in the range 3 to 7 ans = Query(3, 7, 0, n - 1, 1) print(ans.min1) # Query of Type 3 in the range 2 to 5 ans = Query(2, 5, 0, n - 1, 1) print(ans.max1) # Query of Type 1 in the range 1 to 4 RangeUpdate(1, 4, 0, n - 1, 1) # Query of Type 4 in the range 3 to 7 ans = Query(3, 7, 0, n - 1, 1) print(ans.min0) # Query of Type 5 in the range 4 to 9 ans = Query(4, 9, 0, n - 1, 1) print(ans.max0) # This code is contributed by sanjeev2552
Producción:
2 2 3 2
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA