Descripción del problema

Se tiene un arreglo con n elementos, cada uno inicializado en 0. Existen m instrucciones que pueden realizar dos operaciones:

• Invertir los valores en un rango continuo [L, R] (los 0 se convierten en 1 y los 1 en 0) (Operación 1)
• Consultar el valor de un elemento específico (Operación 2)

Por ejemplo, cuando n = 20, las 10 instrucciones son las siguientes:

Formato de entrada

La primera línea contiane dos enteros n, m, que representan la longitud del arreglo y el número de instrucciones. Las siguientes m líneas, cada una comienza con un número t que indica el tipo de operación:

• Si t = 1, entonces siguen dos números L, R, indicando que cada número en el intervalo [L, R] debe ser invertido.
• Si t = 2, entonces sigue un solo número i, indicando el índice del elemento a consultar.

Formato de salida

Para cada operación de tipo 2, se debe imprmiir una línea (con valor 0 o 1), que corresponda al resultado de la consulta.

Ejemplo de entrada y salida

Entrada #1 ``` 20 10 1 1 10 2 6 2 12 1 5 12 2 6 2 15 1 6 16 1 11 17 2 12 2 6

Salida #1 ```
1
0
0
0
1
1

Explicación

Este es un problema plantilla para el Árbol Binario Indexado (Fenwick Tree). La solución aprovecha una propiedad interesante: al sumar 1 a un rango, cambiamos la paridad de los valores, que a su vez se puede mapear a 0/1.

El código implementa esta solución utilizando un Fenwick Tree para realizar actualizaciones de rango y consultas puntuales. La idea clave es almacenar la paridad (mod 2) del número de veces que cada posición ha sido invertida.

Código :

 1 #include <bits/stdc++.h>
 2 #define rapido ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 3 using namespace std;
 4 
 5 template <typename T>
 6 class ArbolBinario {
 7     public:
 8     vector<T> estructura;
 9     int tamanio;
10     ArbolBinario(int _n) : tamanio(_n) {
11         estructura.resize(tamanio);
12     }
13     void modificar(int posicion, T valor) {
14         while (posicion < tamanio) {
15             estructura[posicion] += valor;
16             posicion |= (posicion + 1);
17         }
18     }
19     T consultar(int posicion) {
20         T resultado{};
21         while (posicion >= 0) {
22             resultado += estructura[posicion];
23             posicion = (posicion & (posicion + 1)) - 1;
24         }
25         return resultado;
26     }
27     T obtenerRango(int inicio, int fin) {
28         return consultar(fin) - consultar(inicio - 1);
29     }
30 };
31 
32 int32_t main() { 
33     rapido;
34     int n, m;
35     cin >> n >> m;
36     ArbolBinario<int64_t> arbol(n + 1);
37     for (int i = 1; i <= m; i++) {
38         int operacion;
39         cin >> operacion;
40         if (operacion == 1) {
41             int izquierda, derecha;
42             cin >> izquierda >> derecha;
43             arbol.modificar(izquierda, 1);
44             arbol.modificar(derecha + 1, -1);
45         } else {
46             int posicion;
47             cin >> posicion;
48             cout << arbol.consultar(posicion) % 2 << endl;
49         }
50     }
51 }