Planteamiento del Problema

Sea una secuencia de valores \\(V_1, V_2, \dots, V_N\\). Definimos el valor de un intervalo \\([l, r]\\) (donde \\(l < r\\)) como:

Estrategia de Solución

Observamos que el valor máximo se alcanza cuando \\(V_i\\) es el máximo del intervalo, \\(V_j\\) es el mínimo, y \\(V_k \oplus V_m\\) es el mínimo posible. Para encontrar el mínimo XOR entre dos elementos de un conjunto, basta considerar elementos adyacentes después de ordenar el conjunto.

Mantenemos dos estructuras: una para los valores ordenados del intervalo actual y otra para los valores XOR entre elementos consecutivos. Utilizando la técnica de dos punteros, podemos contar eficientemente cuántos intervalos tienen valor mayor o igual a un umbral \\(x\\). La respuesta para cada consulta se obtiane por diferencia de prefijos.

Complejidad espacial: \\(O(N)\\)
Complejidad temporal: \\(O(QN\log N)\\)

Implementación

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int TAM = 50001;

i64 valores[TAM];
multiset<i64> ordenados, xorAdyacentes;

void agregar(i64 elem) {
  auto it = ordenados.lower_bound(elem);
  if(it != ordenados.begin() && it != ordenados.end()) {
    xorAdyacentes.erase(xorAdyacentes.find((*prev(it)) ^ (*it)));
  }
  if(it != ordenados.begin()) {
    xorAdyacentes.insert((*prev(it)) ^ elem);
  }
  if(it != ordenados.end()) {
    xorAdyacentes.insert((*it) ^ elem);
  }
  ordenados.insert(elem);
}

void eliminar(i64 elem) {
  auto it = ordenados.lower_bound(elem);
  if(it != ordenados.begin() && it != ordenados.end()) {
    xorAdyacentes.insert((*prev(it)) ^ (*it));
  }
  if(it != ordenados.begin()) {
    xorAdyacentes.erase(xorAdyacentes.find((*prev(it)) ^ elem));
  }
  if(it != ordenados.end()) {
    xorAdyacentes.erase(xorAdyacentes.find((*it) ^ elem));
  }
  ordenados.erase(ordenados.find(elem));
}

i64 contarIntervalos(i64 umbral) {
  ordenados.clear(), xorAdyacentes.clear();
  agregar(valores[1]);
  i64 total = 0;
  for(int inicio = 1, fin = 1; inicio <= n; eliminar(valores[inicio]), ++inicio) {
    for(; fin <= n && (xorAdyacentes.empty() || *prev(ordenados.end()) - *ordenados.begin() - *xorAdyacentes.begin() < umbral); ) {
      if(++fin <= n) {
        agregar(valores[fin]);
      }
    }
    total += (n - fin + 1);
  }
  return total;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, q;
  cin >> n >> q;
  for(int i = 1; i <= n; ++i) {
    cin >> valores[i];
  }
  while(q--) {
    i64 limiteInf, limiteSup;
    cin >> limiteInf >> limiteSup;
    cout << contarIntervalos(limiteInf) - contarIntervalos(limiteSup + 1) << "\n";
  }
  return 0;
}

Configuraciones de Dispositivos Mágicos

Planteamiento del Problema

Debemos organizar \\(N\\) dispositivos mágicos en un círculo. Si los dispositivos \\(i\\) y \\(j\\) son adyacentes, forman un canal con valor mágico \\(m_{i,j}\\). Una configuración es estable si la diferencia entre cualquier par de valores de canales no excede \\(k\\). Algunas posiciones ya están predeterminadas. ¿Cuántas configuraciones estables existen?

Estrategia de Solución

Para simplificar, rotamos el círculo para fijar el primer dispositivo. Si no hay dispositivos fijos, asignamos arbitrariamente el dispositivo 1 a la primera posición y multiplicaremos el resultado final por \\(N\\).

Enumeramos el posible valor mínimo \\(x\\) de los canales. Definimos \\(dp[flag, mascara, ultimo]\\) donde:
- \\(flag\\) indica si ya hemos utilizado un canal con valor \\(x\\)
- \\(mascara\\) representa el conjunto de dispositivos ya colocados
- \\(ultimo\\) es el último dispositivo colocado

Esta dimensión \\(flag\\) evita conteos duplicados. La transición entre estados considera adding un nuevo dispositivo que cumpla con las restricciones de estabilidad.

Complejidad espacial: \\(O(N2^N)\\)
Complejidad temporal: \\(O(N^3 2^N)\\)

Implementación

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 14, MODULO = 998244353;

int n, k;
int dispositivo[MAX_N];
int valoresCanales[MAX_N][MAX_N];
int todosValores[MAX_N * MAX_N / 2], contadorValores;
int dp[2][1 << MAX_N][MAX_N];
int respuesta;

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> k;
  
  int posicionFija = 0;
  bool tieneFijo = false;
  
  for(int i = 1; i <= n; ++i) {
    cin >> dispositivo[i];
    if(dispositivo[i]) {
      tieneFijo = true;
      posicionFija = i;
    }
  }
  
  int dispositivosRotados[MAX_N];
  if(tieneFijo) {
    for(int i = 1; i <= n; ++i) {
      int nuevaPos = i >= posicionFija ? i - posicionFija + 1 : n - posicionFija + 1 + i;
      dispositivosRotados[nuevaPos] = dispositivo[i];
    }
  } else {
    dispositivosRotados[1] = 1;
  }
  
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
      cin >> valoresCanales[i][j];
      if(j < i) {
        todosValores[contadorValores++] = valoresCanales[i][j];
      }
    }
  }
  
  sort(todosValores, todosValores + contadorValores);
  
  for(int idxValor = 0; idxValor < contadorValores; ++idxValor) {
    int valorMin = todosValores[idxValor];
    
    for(int estado = 0; estado < 2; ++estado) {
      for(int mascara = 0; mascara < (1 << n); ++mascara) {
        fill(dp[estado][mascara], dp[estado][mascara] + n, 0);
      }
    }
    
    dp[0][1 << (dispositivosRotados[1] - 1)][dispositivosRotados[1]] = 1;
    
    for(int mascara = 1; mascara < (1 << n); ++mascara) {
      for(int estado = 0; estado < 2; ++estado) {
        int count = __builtin_popcount(mascara);
        for(int actual = 1; actual <= n; ++actual) {
          if(!dp[estado][mascara][actual]) continue;
          
          for(int siguiente = 1; siguiente <= n; ++siguiente) {
            if((mascara >> (siguiente - 1)) & 1) continue;
            if(dispositivosRotados[count + 1] && dispositivosRotados[count + 1] != siguiente) continue;
            
            int valorCanal = valoresCanales[actual][siguiente];
            if(valorCanal < valorMin || valorCanal - valorMin > k) continue;
            
            int nuevoEstado = estado | (valorCanal == valorMin);
            int nuevaMascara = mascara | (1 << (siguiente - 1));
            dp[nuevoEstado][nuevaMascara][siguiente] = 
              (dp[nuevoEstado][nuevaMascara][siguiente] + dp[estado][mascara][actual]) % MODULO;
          }
        }
      }
    }
    
    int mascaraCompleta = (1 << n) - 1;
    for(int ultimo = 1; ultimo <= n; ++ultimo) {
      int valorCanalCierre = valoresCanales[ultimo][dispositivosRotados[1]];
      if(valorCanalCierre < valorMin || valorCanalCierre - valorMin > k) continue;
      
      respuesta = (respuesta + dp[1][mascaraCompleta][ultimo]) % MODULO;
      if(valorCanalCierre == valorMin) {
        respuesta = (respuesta + dp[0][mascaraCompleta][ultimo]) % MODULO;
      }
    }
  }
  
  if(!tieneFijo) {
    respuesta = (i64)respuesta * n % MODULO;
  }
  
  cout << respuesta;
  return 0;
}