En el análisis de complejidad del algoritmo de Mo estándar, para $Q$ consultas donde cada desplazamiento de los punteros mantiene una longitud de $O(\sqrt{n})$ y cada operación de inserción o eliminación cuesta $O(k)$, el tiempo total es $O(Qk\sqrt{n})$.
Mo con Reversión (Rollback Mo)
El algoritmo de Mo convnecional exige que tanto la inserción como la eliminación tengan complejidad $O(k)$. Sin embargo, existen problemas donde la eliminación no puede actualizarse eficientemente. Considérese el siguiente problema clásico:
Dada una secuencia de longitud $n$, con $Q$ consultas que preguntan por la máxima distancia entre dos elementos iguales dentro del rango $[l,r]$.
Se mantienen dos arreglos de extremos: uno almacena la primera aparición de cada valor y otro la última aparición dentro del rango actual $[l,r]$. Al insertar una posición, se actualizan ambos extremos y luego el resultado global. La inserción es directa: al expandir de $[l,r]$ a $[l,r+1]$, se actualiza el arreglo con $a[r+1]$ y se verifica si mejora la respuesta.
Sin embargo, al eliminar —por ejemplo, al contraer $[l,r]$ a $[l,r-1]$— los extremos pueden revertirse usando una pila de operaciones, pero la respuesta global podría disminuir y no es posible hallar el segundo mejor valor en $O(1)$.
Estrategia: diseñar un esquema que solo realice inserciones.
Se enumeran los bloques de los punteros izquierdo y derecho, denotados $[bx, br]$. Primero se precomputa la respuesta para el bloque intermedio $[bx+1, br-1]$. Para cada consulta dentro de $[bx, br]$, se expande hacia la izquierda desde el inicio de $bx+1$ y hacia la derecha desde el final de $br-1$, calculando la respuesta y luego revirtiendo todos los cambios. Al avanzar $br$, se extiende la respuesta precomputada de $[bx-1, br-1]$ a $[bx-1, br]$. Al mover $bx$ hacia la derecha, se reinicia todo el proceso desde cero.
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 400005;
const int INF = 0x3f3f3f3f;
int seqLen, numQueries, blockSize, numBlocks, numVals;
int rawArr[MAXN], compArr[MAXN], sortedVals[MAXN];
int blockId[MAXN], blockStart[MAXN], blockEnd[MAXN];
struct Query {
int left, right, result, idx;
} queries[MAXN];
bool sortByBlock(const Query &a, const Query &b) {
if (blockId[a.left] != blockId[b.left]) return blockId[a.left] < blockId[b.left];
return blockId[a.right] < blockId[b.right];
}
bool sortByIdx(const Query &a, const Query &b) {
return a.idx < b.idx;
}
int bestAns, opTop;
struct Snapshot { int pos, prevMin, prevMax; } history[MAXN];
int minPos[MAXN], maxPos[MAXN];
void insertPos(int pos) {
history[++opTop] = {pos, minPos[compArr[pos]], maxPos[compArr[pos]]};
minPos[compArr[pos]] = min(minPos[compArr[pos]], pos);
maxPos[compArr[pos]] = max(maxPos[compArr[pos]], pos);
bestAns = max(bestAns, maxPos[compArr[pos]] - minPos[compArr[pos]]);
}
void removePos(int pos) {
minPos[compArr[pos]] = history[opTop].prevMin;
maxPos[compArr[pos]] = history[opTop].prevMax;
opTop--;
}
int main() {
scanf("%d", &seqLen);
for (int i = 1; i <= seqLen; i++) {
scanf("%d", &rawArr[i]);
sortedVals[i] = rawArr[i];
blockId[i] = (i - 1) / 500 + 1;
}
for (int i = 1; i <= blockId[seqLen]; i++) {
blockStart[i] = (i - 1) * 500 + 1;
blockEnd[i] = min(i * 500, seqLen);
}
scanf("%d", &numQueries);
for (int i = 1; i <= numQueries; i++) {
scanf("%d%d", &queries[i].left, &queries[i].right);
queries[i].idx = i;
}
sort(sortedVals + 1, sortedVals + seqLen + 1);
for (int i = 1; i <= seqLen; i++)
if (i == 1 || sortedVals[i] != sortedVals[i - 1])
compArr[++numVals] = sortedVals[i];
// coordinate compression
int tmp[MAXN];
for (int i = 1; i <= seqLen; i++)
tmp[i] = lower_bound(compArr + 1, compArr + numVals + 1, rawArr[i]) - compArr;
for (int i = 1; i <= seqLen; i++) compArr[i] = tmp[i];
for (int i = 1; i <= numVals; i++) { minPos[i] = seqLen + 1; maxPos[i] = 0; }
sort(queries + 1, queries + numQueries + 1, sortByBlock);
int qPtr = 1;
for (int bl = 1; bl <= blockId[seqLen]; bl++) {
// queries within same block
for (; qPtr <= numQueries && blockId[queries[qPtr].left] == bl && blockId[queries[qPtr].right] == bl; qPtr++) {
bestAns = 0;
for (int j = queries[qPtr].left; j <= queries[qPtr].right; j++) insertPos(j);
queries[qPtr].result = bestAns;
for (int j = queries[qPtr].right; j >= queries[qPtr].left; j--) removePos(j);
}
int curL = blockEnd[bl] + 1, curR = blockEnd[bl];
bestAns = 0;
for (int br = bl + 1; br <= blockId[seqLen]; br++) {
for (; qPtr <= numQueries && blockId[queries[qPtr].left] == bl && blockId[queries[qPtr].right] == br; qPtr++) {
int saved = bestAns;
for (int p = blockEnd[bl]; p >= queries[qPtr].left; p--) insertPos(p);
for (int p = blockStart[br]; p <= queries[qPtr].right; p++) insertPos(p);
queries[qPtr].result = bestAns;
for (int p = queries[qPtr].right; p >= blockStart[br]; p--) removePos(p);
for (int p = queries[qPtr].left; p <= blockEnd[bl]; p++) removePos(p);
bestAns = saved;
}
for (; curR + 1 <= blockEnd[br]; curR++) insertPos(curR + 1);
}
for (; curR >= curL; curR--) removePos(curR);
}
sort(queries + 1, queries + numQueries + 1, sortByIdx);
for (int i = 1; i <= numQueries; i++) printf("%d\n", queries[i].result);
return 0;
}
Mo de Doble Desconexión (Second-order Offline Mo)
Considérese el siguiente problema: dada una secuencia $a$ de longitud $n$, un entero $K$ y $Q$ consultas. Para cada consulta $[l,r]$, contar los pares $(i,j)$ con $l \le i < j \le r$ tales que $a[i] \oplus a[j]$ tiene exactamente $K$ bits encendidos, con $a[i] \le 2^{14}$.
Con Mo estándar, se mantiene un contador de frecuencias donde para cada elemento en el rango $[l,r]$ se registra cuántas veces aparece $a[i] \oplus K$. Cada inserción o eliminación requiere actualizar el bucket en $O(C_{14}^{K})$, resultando en $O(C_{14}^{K} \cdot n\sqrt{n})$, lo cual es inviable.
La técnica de doble desconexión, desarrollada por lxl, aprovecha la capacidad de diferenciar las contribuciones. Al expandir de $[l,r]$ a $[l,r+x]$, la contribución total es:
$\sum_{i=r+1}^{r+x} f(i, [l, i-1]) = \sum_{i=r+1}^{r+x} f(i, [1, i-1]) - \sum_{i=r+1}^{r+x} f(i, [1, l-1])$
donde $f(x, [a,b])$ representa el número de elementos en $[a,b]$ que forman un par válido con $x$.
El primer término se precomputa en $O(C_{14}^{K} \cdot n)$ recorriendo la secuencia de izquiedra a derecha, manteniendo el bucket incrementalmente. El segundo término se gestiona colgando los rangos $[r+1, r+x]$ en la posición $l-1$ mediante vectores. Al iterar $l$ de izquierda a derecha, se actualiza el bucket y se responden todas las consultas pendientes en esa posición.
Las expansiones hacia la izquierda, así como las inserciones y eliminaciones, se tratan de forma análoga. La complejidad total es $O(kn + n\sqrt{n})$.
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN = 200005;
int n, q, K, sq, candidateCount;
int arr[MAXN], candidates[MAXN], popcount[1 << 14], blockId[MAXN];
ll contribution[MAXN], freq[1 << 14];
struct Query {
int lo, hi, idx;
ll res;
} qry[MAXN];
bool cmpBlock(const Query &a, const Query &b) {
if (blockId[a.lo] != blockId[b.lo]) return blockId[a.lo] < blockId[b.lo];
return blockId[a.hi] < blockId[b.hi];
}
bool cmpIdx(const Query &a, const Query &b) { return a.idx < b.idx; }
struct PendingQuery { int from, to, qid, sign; };
vector<PendingQuery> leftPending[MAXN], rightPending[MAXN];
ll leftContrib[MAXN], rightContrib[MAXN];
void processMoves() {
int curLo = 1, curHi = 1;
for (int i = 1; i <= q; i++) {
if (curHi < qry[i].hi) {
leftPending[curLo - 1].push_back({curHi + 1, qry[i].hi, i, 1});
curHi = qry[i].hi;
}
if (curLo > qry[i].lo) {
rightPending[curHi + 1].push_back({qry[i].lo, curLo - 1, i, 1});
curLo = qry[i].lo;
}
if (curLo < qry[i].lo) {
rightPending[curHi + 1].push_back({curLo, qry[i].lo - 1, i, -1});
curLo = qry[i].lo;
}
if (curHi > qry[i].hi) {
leftPending[curLo - 1].push_back({qry[i].hi + 1, curHi, i, -1});
curHi = qry[i].hi;
}
}
// Left-to-right sweep for prefix contributions
for (int pos = 1; pos <= n; pos++) {
leftContrib[pos] += freq[arr[pos]];
for (int c = 1; c <= candidateCount; c++) freq[arr[pos] ^ candidates[c]]++;
for (auto &pq : leftPending[pos]) {
ll sum = 0;
for (int i = pq.from; i <= pq.to; i++) sum += freq[arr[i]];
contribution[pq.qid] += sum * pq.sign * (-1);
}
}
memset(freq, 0, sizeof(freq));
// Right-to-left sweep for suffix contributions
for (int pos = n; pos >= 1; pos--) {
rightContrib[pos] += freq[arr[pos]];
for (int c = 1; c <= candidateCount; c++) freq[arr[pos] ^ candidates[c]]++;
for (auto &pq : rightPending[pos]) {
ll sum = 0;
for (int i = pq.from; i <= pq.to; i++) sum += freq[arr[i]];
contribution[pq.qid] += sum * pq.sign * (-1);
}
}
}
void executeQueries() {
int curLo = 1, curHi = 1;
ll ans = 0;
for (int i = 1; i <= q; i++) {
ans += contribution[i];
if (curHi < qry[i].hi)
for (; curHi + 1 <= qry[i].hi; curHi++) ans += leftContrib[curHi + 1];
if (curLo > qry[i].lo)
for (; curLo - 1 >= qry[i].lo; curLo--) ans += rightContrib[curLo - 1];
if (curLo < qry[i].lo)
for (; curLo + 1 <= qry[i].lo; curLo++) ans -= rightContrib[curLo];
if (curHi > qry[i].hi)
for (; curHi - 1 >= qry[i].hi; curHi--) ans -= leftContrib[curHi];
qry[i].res = ans;
}
}
int main() {
scanf("%d%d%d", &n, &q, &K);
sq = sqrt(n);
for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
for (int i = 1; i <= n; i++) blockId[i] = (i - 1) / sq + 1;
for (int i = 0; i < (1 << 14); i++) {
popcount[i] = popcount[i >> 1] + (i & 1);
if (popcount[i] == K) candidates[++candidateCount] = i;
}
for (int i = 1; i <= q; i++) {
scanf("%d%d", &qry[i].lo, &qry[i].hi);
qry[i].idx = i;
}
sort(qry + 1, qry + q + 1, cmpBlock);
processMoves();
executeQueries();
sort(qry + 1, qry + q + 1, cmpIdx);
for (int i = 1; i <= q; i++) printf("%lld\n", qry[i].res);
return 0;
}