Primer problema: Conteo de elementos distintos en un intervalo

Dado un arreglo estático de números, se realizan múltiples consultas para determinar la cantidad de números distintos presentes en un intervalo [L, R]. La solución utiliza procesamiento offline, donde las consultas se ordenan por su límite derecho. Se mantiene un árbol de Fenwick (arreglo de bits) para registrar la contribución de cada posición.

La idea clave es que, al mover el límite derecho de la consulta, solo la última aparición de cada número es relevante. Si un número ya ha aparecido anteriormente, se elimina su contribución previa y se actualiza la posición actual. Esto permite responder cada consulta en tiempo logarítmico.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_TAM = 1e6 + 10;
int arreglo[MAX_TAM];
int arbol[MAX_TAM];
int ultimaPos[MAX_TAM];
int resultados[MAX_TAM];
int tam, numConsultas;

struct Consulta { int izquierda, derecha, id; };

int bitBajo(int x) { return x & (-x); }

void actualizar(int pos, int valor) {
    while (pos <= tam) {
        arbol[pos] += valor;
        pos += bitBajo(pos);
    }
}

int obtenerSuma(int pos) {
    int suma = 0;
    while (pos > 0) {
        suma += arbol[pos];
        pos -= bitBajo(pos);
    }
    return suma;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> tam;
    for (int i = 1; i <= tam; ++i) cin >> arreglo[i];
    cin >> numConsultas;
    vector<Consulta> consultas(numConsultas);
    for (int i = 0; i < numConsultas; ++i) {
        cin >> consultas[i].izquierda >> consultas[i].derecha;
        consultas[i].id = i;
    }
    sort(consultas.begin(), consultas.end(), [](const Consulta& a, const Consulta& b) {
        return a.derecha < b.derecha;
    });
    int ptr = 0;
    for (int i = 1; i <= tam; ++i) {
        int valor = arreglo[i];
        if (ultimaPos[valor] != 0) actualizar(ultimaPos[valor], -1);
        actualizar(i, 1);
        ultimaPos[valor] = i;
        while (ptr < numConsultas && consultas[ptr].derecha == i) {
            resultados[consultas[ptr].id] = obtenerSuma(consultas[ptr].derecha) - obtenerSuma(consultas[ptr].izquierda - 1);
            ptr++;
        }
    }
    for (int i = 0; i < numConsultas; ++i) cout << resultados[i] << "\n";
    return 0;
}

Segundo problema: XOR de elementos con frecuencia par en un intervalo

Se requiere calcular el valor XOR de todos los números que aparecen un número par de veces en un intervalo dado. La solución combina el uso de un árbol de Fenwick con operaciones XOR y prefijos acumulados. La clave es que el XOR de un número consigo mismo es cero, por lo que el resultado se obtiene como el XOR de todos los números distintos en el intervalo con el XOR total del intervalo.

Se procesan las consultas offline ordenadas por el límite derecho. Se mantiene un árbol de Fenwick donde se almacena el XOR de las últimas apariciones. Al encontrar un número, se actualiza su posición anterior a cero (usando XOR) y se establece la nueva posición. Esto garantiza que solo la última aparición contribuya al resultado.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const int MAX_TAM = 1e6 + 10;
int arregloOriginal[MAX_TAM];
int prefijoXOR[MAX_TAM];
int discretizado[MAX_TAM];
int arbol[MAX_TAM];
int ultimaPos[MAX_TAM];
int resultados[MAX_TAM];
int tam, numConsultas, contador;

struct Consulta { int izquierda, derecha, id; };

int bitBajo(int x) { return x & (-x); }

void actualizar(int pos, int valor) {
    while (pos <= tam) {
        arbol[pos] ^= valor;
        pos += bitBajo(pos);
    }
}

int obtenerXOR(int pos) {
    int xorResultado = 0;
    while (pos > 0) {
        xorResultado ^= arbol[pos];
        pos -= bitBajo(pos);
    }
    return xorResultado;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> tam;
    map<int, int> mapeo;
    contador = 0;
    for (int i = 1; i <= tam; ++i) {
        cin >> arregloOriginal[i];
        prefijoXOR[i] = prefijoXOR[i - 1] ^ arregloOriginal[i];
        if (mapeo.find(arregloOriginal[i]) == mapeo.end()) {
            mapeo[arregloOriginal[i]] = ++contador;
            discretizado[contador] = arregloOriginal[i];
        }
        arregloOriginal[i] = mapeo[arregloOriginal[i]];
    }
    cin >> numConsultas;
    vector<Consulta> consultas(numConsultas);
    for (int i = 0; i < numConsultas; ++i) {
        cin >> consultas[i].izquierda >> consultas[i].derecha;
        consultas[i].id = i;
    }
    sort(consultas.begin(), consultas.end(), [](const Consulta& a, const Consulta& b) {
        return a.derecha < b.derecha;
    });
    int ptr = 0;
    for (int i = 1; i <= tam; ++i) {
        int idx = arregloOriginal[i];
        if (ultimaPos[idx] != 0) actualizar(ultimaPos[idx], discretizado[idx]);
        actualizar(i, discretizado[idx]);
        ultimaPos[idx] = i;
        while (ptr < numConsultas && consultas[ptr].derecha == i) {
            int xorDistintos = obtenerXOR(consultas[ptr].derecha) ^ obtenerXOR(consultas[ptr].izquierda - 1);
            int xorTotal = prefijoXOR[consultas[ptr].derecha] ^ prefijoXOR[consultas[ptr].izquierda - 1];
            resultados[consultas[ptr].id] = xorDistintos ^ xorTotal;
            ptr++;
        }
    }
    for (int i = 0; i < numConsultas; ++i) cout << resultados[i] << "\n";
    return 0;
}