As árvores Splay são um tipo de árvore binária de busca auto-balanceada que otimiza o desempenho amortizado das operações. Embora existam outras estruturas como Árvores Rubro-Negras ou Treaps, as Splay trees são notáveis pela sua simplicidade conceitual nas operações de balanceamento, especialmente a rotação e a operação de splay, que garantem que operações recentes sejam mais rápidas ao trazer os nós acessados para mais perto da raiz.
A essência de uma árvore Splay reside na sua capacidade de reorganizar a estrutura da árvore através de rotações após cada acesso ou modificação. Este documento explora os componentes fundamentais e as operações típicas para construir e manipular uma árvore Splay.
Estrutura do Nó da Árvore Splay
Cada nó em uma árvore Splay é representado por uma estrutura que armazena informações essenciais sobre o próprio nó e sua relação com a árvore.
struct SplayNode {
int value; // Valor armazenado no nó
int count; // Número de ocorrências deste valor (para multi-conjuntos)
int subtreeSize; // Tamanho da subárvore enraizada neste nó
int parent; // Índice do nó pai
int children[2]; // Índices dos filhos: children[0] para esquerdo, children[1] para direito
int lazyFlag; // Sinalizador de "lazy propagation", útil para operações em intervalos (e.g., inversão)
};
SplayNode treeNodes[1001010]; // Array para armazenar os nós da árvore
int rootIndex; // Índice da raiz da árvore
int nextFreeNodeIndex; // Próximo índice disponível para um novo nó
Funções Auxiliares Essenciais
Atualização do Tamanho da Subárvore
A função updateNodeSize recalcula o campo subtreeSize de um nó, garantindo que ele reflita corretamente o tamanho de sua subárvore (incluindo ele mesmo e todos os seus descendentes). Isso é crucial após qualquer modificação na estrutura da árvore.
void updateNodeSize(int nodeIdx) {
treeNodes[nodeIdx].subtreeSize = treeNodes[treeNodes[nodeIdx].children[0]].subtreeSize +
treeNodes[treeNodes[nodeIdx].children[1]].subtreeSize +
treeNodes[nodeIdx].count;
}
Verificação de Posição do Filho
A função isRightChild determina se um nó é o filho direito de seu pai. Isso simplifica a lógica das operações de rotação.
bool isRightChild(int nodeIdx) {
return treeNodes[treeNodes[nodeIdx].parent].children[1] == nodeIdx;
}
Conexão de Nós
A função linkNodes é uma utilitário para estabelecer as conexões pai-filho entre dois nós, especificando a direção (esquerda ou direita) da conexão.
void linkNodes(int childIdx, int parentIdx, int direction) {
treeNodes[parentIdx].children[direction] = childIdx;
if (childIdx != 0) { // Verifica se o filho não é nulo
treeNodes[childIdx].parent = parentIdx;
}
}
Propagação de Sinalizadores (Pushdown)
Para operações de intervalo, como inversões de sequência, um lazyFlag é usado. A função pushLazyTag propaga este sinalizador para os filhos de um nó e realiza a operação correspondente (e.g., troca os filhos para uma inversão), limpando o sinalizador no nó atual.
void pushLazyTag(int nodeIdx) {
if (treeNodes[nodeIdx].lazyFlag != 0) {
// Inverte os sinalizadores de lazy nos filhos
treeNodes[treeNodes[nodeIdx].children[0]].lazyFlag ^= 1;
treeNodes[treeNodes[nodeIdx].children[1]].lazyFlag ^= 1;
// Troca os filhos esquerdo e direito
std::swap(treeNodes[nodeIdx].children[0], treeNodes[nodeIdx].children[1]);
// Limpa o sinalizador no nó atual
treeNodes[nodeIdx].lazyFlag = 0;
}
}
Operações de Balanceamento
Rotação (Rotate)
A operação de rotação é o mecanismo fundamental para reestruturar a árvore, mantendo as propriedades de árvore binária de busca. Ela move um nó para cima na árvore sem alterar a ordem de sua travessia em-ordem.
void rotate(int nodeIdx) {
int parentIdx = treeNodes[nodeIdx].parent;
int grandParentIdx = treeNodes[parentIdx].parent;
// Determina se nodeIdx é filho direito ou esquerdo de parentIdx
bool isNodeRightChild = isRightChild(nodeIdx);
// Determina se parentIdx é filho direito ou esquerdo de grandParentIdx
bool isParentRightChild = isRightChild(parentIdx);
// Conecta o filho oposto do nó ao pai
linkNodes(treeNodes[nodeIdx].children[!isNodeRightChild], parentIdx, isNodeRightChild);
// Conecta o pai ao nó
linkNodes(parentIdx, nodeIdx, !isNodeRightChild);
// Conecta o nó ao avô
linkNodes(nodeIdx, grandParentIdx, isParentRightChild);
// Atualiza os tamanhos dos nós envolvidos, começando pelo que subiu (o pai original)
updateNodeSize(parentIdx);
updateNodeSize(nodeIdx);
}
Splay
A operação de splay move um nó especificado para uma posição desejada na árvore, geralmente a raiz, através de uma série de rotações. Isso garante que nós frequentemente acessados fiquem próximos à raiz, melhorando o desempenho amortizado.
void splay(int nodeIdx, int targetParentIdx) {
while (treeNodes[nodeIdx].parent != targetParentIdx) {
int parentIdx = treeNodes[nodeIdx].parent;
int grandParentIdx = treeNodes[parentIdx].parent;
// Propaga lazy tags antes de rotações para garantir que a estrutura esteja atualizada
if (grandParentIdx != 0) pushLazyTag(grandParentIdx);
pushLazyTag(parentIdx);
pushLazyTag(nodeIdx);
if (grandParentIdx != targetParentIdx) {
// Caso Zig-Zig ou Zig-Zag
bool nodeIsRight = isRightChild(nodeIdx);
bool parentIsRight = isRightChild(parentIdx);
if (nodeIsRight == parentIsRight) { // Zig-Zig
rotate(parentIdx);
} else { // Zig-Zag
rotate(nodeIdx);
}
}
rotate(nodeIdx); // A última rotação sempre eleva o nó atual
}
// Se o alvo não for a raiz, atualiza a raiz da árvore
if (targetParentIdx == 0) {
rootIndex = nodeIdx;
}
}
Operações de Manipulação de Dados
Inserir um Valor
Para inserir um novo valor, percorremos a árvore como em uma BST normal até encontrar o local apropriado. Se o valor já existe, incrementamos sua contagem. Caso contrário, criamos um novo nó. Após a inserção, realizamos uma operação de splay no nó inserido para trazê-lo à raiz.
void insertValue(int valueToInsert) {
int currentIdx = rootIndex;
int parentIdx = 0;
// Encontra o local de inserção ou a ocorrência existente
while (currentIdx != 0 && treeNodes[currentIdx].value != valueToInsert) {
pushLazyTag(currentIdx); // Propaga tags antes de descer
parentIdx = currentIdx;
currentIdx = treeNodes[currentIdx].children[treeNodes[currentIdx].value < valueToInsert];
}
if (currentIdx != 0) { // O valor já existe
treeNodes[currentIdx].count++;
} else { // Cria um novo nó
currentIdx = ++nextFreeNodeIndex;
if (parentIdx != 0) {
linkNodes(currentIdx, parentIdx, treeNodes[parentIdx].value < valueToInsert);
}
treeNodes[currentIdx] = {valueToInsert, 1, 1, parentIdx, {0, 0}, 0};
}
splay(currentIdx, 0); // Traz o nó inserido para a raiz
}
Buscar um Nó
A função findNode localiza o nó que contém um valor específico. Ela percorre a árvore seguindo a lógica de uma BST.
int findNode(int valueToFind) {
int currentIdx = rootIndex;
while (currentIdx != 0 && treeNodes[currentIdx].value != valueToFind) {
pushLazyTag(currentIdx); // Propaga tags ao percorrer
currentIdx = treeNodes[currentIdx].children[treeNodes[currentIdx].value < valueToFind];
}
return currentIdx;
}
Obter o Rank de um Valor
O rank de um valor é o número de elementos na árvore menores ou iguais a ele. Para obter o rank, primeiro realizamos um splay no nó que contém o valor (ou o mais próximo) para a raiz, e então contamos os elementos na subárvore esquerda.
int getRankOfValue(int value) {
int foundNodeIdx = findNode(value);
if (foundNodeIdx == 0) return 0; // Valor não encontrado
splay(foundNodeIdx, 0); // Traz o nó encontrado para a raiz
// O rank é o tamanho da subárvore esquerda
return treeNodes[treeNodes[rootIndex].children[0]].subtreeSize;
}
Obter Valer por Rank
Esta função retorna o valor do k-ésimo menor elemento na árvore. Ela percorre a árvore, ajustando o rank com base nos tamanhos das subárvores.
int getValueByRank(int rank) {
int currentIdx = rootIndex;
while (true) {
pushLazyTag(currentIdx); // Propaga tags antes de tomar decisões
int leftChildSize = treeNodes[treeNodes[currentIdx].children[0]].subtreeSize;
if (rank <= leftChildSize) { // O k-ésimo elemento está na subárvore esquerda
currentIdx = treeNodes[currentIdx].children[0];
} else if (rank > leftChildSize + treeNodes[currentIdx].count) { // O k-ésimo elemento está na subárvore direita
rank -= (leftChildSize + treeNodes[currentIdx].count);
currentIdx = treeNodes[currentIdx].children[1];
} else { // O k-ésimo elemento é o próprio nó atual
splay(currentIdx, 0); // Opcional: traz o nó para a raiz
return treeNodes[currentIdx].value;
}
}
}
Encontrar Predecessor ou Sucessor
Para encontrar o predecessor (maior valor menor que v) ou o sucessor (menor valor maior que v), primeiro splayamos o nó correspondente a v (ou o mais próximo) para a raiz. Em seguida, procuramos o nó mais à direita na subárvore esquerda para o predecessor, ou o nó mais à esquerda na subárvore direita para o sucessor.
int findAdjacentNode(int value, bool findSuccessor) { // findSuccessor = true para sucessor, false para predecessor
splay(findNode(value), 0); // Splay o nó mais próximo (ou o próprio) para a raiz
int currentIdx = rootIndex;
if (findSuccessor) {
// Se o valor na raiz for maior que o procurado, a raiz pode ser o sucessor
if (treeNodes[currentIdx].value > value) return currentIdx;
currentIdx = treeNodes[currentIdx].children[1]; // Vai para a subárvore direita
while (treeNodes[currentIdx].children[0] != 0) {
pushLazyTag(currentIdx);
currentIdx = treeNodes[currentIdx].children[0]; // Busca o menor na subárvore direita
}
} else { // Buscar predecessor
// Se o valor na raiz for menor que o procurado, a raiz pode ser o predecessor
if (treeNodes[currentIdx].value < value) return currentIdx;
currentIdx = treeNodes[currentIdx].children[0]; // Vai para a subárvore esquerda
while (treeNodes[currentIdx].children[1] != 0) {
pushLazyTag(currentIdx);
currentIdx = treeNodes[currentIdx].children[1]; // Busca o maior na subárvore esquerda
}
}
return currentIdx;
}
Deletar um Valor
A remoção de um valor envolve identificar o nó a ser removido. Se houver múltiplas ocorrências (count > 1), simplesmente decrementamos o contador. Caso contrário, precisamos reorganizar a árvore. Isso é feito splayando o predecessor do nó para a raiz, e o sucessor do nó para ser filho direito da raiz. O nó a ser removido então se torna o filho esquerdo do sucessor e pode ser desconectado. Uma splay final garante que a árvore permaneça balanceada.
void deleteValue(int valueToDelete) {
int predecessorIdx = findAdjacentNode(valueToDelete, false); // Encontra o predecessor
int successorIdx = findAdjacentNode(valueToDelete, true); // Encontra o sucessor
splay(predecessorIdx, 0); // Predecessor para a raiz
splay(successorIdx, predecessorIdx); // Sucessor para ser filho direito do predecessor
int nodeToDeleteIdx = treeNodes[successorIdx].children[0];
if (nodeToDeleteIdx != 0) {
if (treeNodes[nodeToDeleteIdx].count > 1) {
treeNodes[nodeToDeleteIdx].count--;
splay(nodeToDeleteIdx, 0); // Splay o nó com count decrementado para a raiz
} else {
treeNodes[successorIdx].children[0] = 0; // Remove o nó
updateNodeSize(successorIdx);
updateNodeSize(predecessorIdx);
}
}
}
Código Completo de uma Árvore Splay Genérica
Este exemplo implementa as operações básicas para uma árvore Splay que funciona como um multi-conjunto dinâmico.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::swap
const int INF = 2147483647; // Um valor grande para sentinela
struct SplayNode {
int value;
int count;
int subtreeSize;
int parent;
int children[2]; // 0: esquerdo, 1: direito
int lazyFlag; // Não usado na árvore Splay genérica, mas mantido para consistência
};
SplayNode treeNodes[1001010];
int rootIndex;
int nextFreeNodeIndex;
void updateNodeSize(int nodeIdx) {
treeNodes[nodeIdx].subtreeSize = treeNodes[treeNodes[nodeIdx].children[0]].subtreeSize +
treeNodes[treeNodes[nodeIdx].children[1]].subtreeSize +
treeNodes[nodeIdx].count;
}
bool isRightChild(int nodeIdx) {
return treeNodes[treeNodes[nodeIdx].parent].children[1] == nodeIdx;
}
void linkNodes(int childIdx, int parentIdx, int direction) {
treeNodes[parentIdx].children[direction] = childIdx;
if (childIdx != 0) {
treeNodes[childIdx].parent = parentIdx;
}
}
// pushLazyTag não é estritamente necessário para operações básicas, mas é mantido como placeholder
void pushLazyTag(int nodeIdx) {
// Para a Splay Tree genérica, não há lazy tags para propagar.
// Esta função seria implementada para casos específicos como inversão de intervalos.
}
void rotate(int nodeIdx) {
int parentIdx = treeNodes[nodeIdx].parent;
int grandParentIdx = treeNodes[parentIdx].parent;
bool isNodeRight = isRightChild(nodeIdx);
bool isParentRight = isRightChild(parentIdx);
linkNodes(treeNodes[nodeIdx].children[!isNodeRight], parentIdx, isNodeRight);
linkNodes(parentIdx, nodeIdx, !isNodeRight);
linkNodes(nodeIdx, grandParentIdx, isParentRight);
updateNodeSize(parentIdx);
updateNodeSize(nodeIdx);
}
void splay(int nodeIdx, int targetParentIdx) {
while (treeNodes[nodeIdx].parent != targetParentIdx) {
int parentIdx = treeNodes[nodeIdx].parent;
int grandParentIdx = treeNodes[parentIdx].parent;
// Em um splay genérico, pushLazyTag pode não ser chamado aqui,
// mas em árvores que usam lazy tags para operações em intervalos, é crucial.
// if (grandParentIdx != 0) pushLazyTag(grandParentIdx);
// pushLazyTag(parentIdx);
// pushLazyTag(nodeIdx);
if (grandParentIdx != targetParentIdx) {
bool nodeIsRight = isRightChild(nodeIdx);
bool parentIsRight = isRightChild(parentIdx);
if (nodeIsRight == parentIsRight) { // Zig-Zig
rotate(parentIdx);
} else { // Zig-Zag
rotate(nodeIdx);
}
}
rotate(nodeIdx);
}
if (targetParentIdx == 0) {
rootIndex = nodeIdx;
}
}
void insertValue(int valueToInsert) {
int currentIdx = rootIndex;
int parentIdx = 0;
while (currentIdx != 0 && treeNodes[currentIdx].value != valueToInsert) {
parentIdx = currentIdx;
currentIdx = treeNodes[currentIdx].children[treeNodes[currentIdx].value < valueToInsert];
}
if (currentIdx != 0) {
treeNodes[currentIdx].count++;
} else {
currentIdx = ++nextFreeNodeIndex;
if (parentIdx != 0) {
linkNodes(currentIdx, parentIdx, treeNodes[parentIdx].value < valueToInsert);
}
treeNodes[currentIdx] = {valueToInsert, 1, 1, parentIdx, {0, 0}, 0};
}
splay(currentIdx, 0);
}
int findNode(int valueToFind) {
int currentIdx = rootIndex;
while (currentIdx != 0 && treeNodes[currentIdx].value != valueToFind) {
currentIdx = treeNodes[currentIdx].children[treeNodes[currentIdx].value < valueToFind];
}
return currentIdx;
}
int getRankOfValue(int value) {
splay(findNode(value), 0);
return treeNodes[treeNodes[rootIndex].children[0]].subtreeSize;
}
int getValueByRank(int rank) {
int currentIdx = rootIndex;
while (true) {
// pushLazyTag(currentIdx); // Não necessário para Splay genérica sem operações de intervalo
int leftChildSize = treeNodes[treeNodes[currentIdx].children[0]].subtreeSize;
if (rank <= leftChildSize) {
currentIdx = treeNodes[currentIdx].children[0];
} else if (rank > leftChildSize + treeNodes[currentIdx].count) {
rank -= (leftChildSize + treeNodes[currentIdx].count);
currentIdx = treeNodes[currentIdx].children[1];
} else {
splay(currentIdx, 0); // Traz o nó para a raiz
return treeNodes[currentIdx].value;
}
}
}
int findAdjacentNode(int value, bool findSuccessor) {
int foundNode = findNode(value);
if(foundNode == 0) { // If value is not present, find the node that would be its parent
insertValue(value); // Temporarily insert to find position
foundNode = rootIndex; // The inserted node is now the root
deleteValue(value); // Delete it immediately after finding its logical place
splay(foundNode, 0); // Restore original root
} else {
splay(foundNode, 0);
}
int currentIdx = rootIndex;
if (findSuccessor) {
if (treeNodes[currentIdx].value > value) return currentIdx; // Root itself might be the successor
currentIdx = treeNodes[currentIdx].children[1];
while (treeNodes[currentIdx].children[0] != 0) {
currentIdx = treeNodes[currentIdx].children[0];
}
} else { // Find predecessor
if (treeNodes[currentIdx].value < value) return currentIdx; // Root itself might be the predecessor
currentIdx = treeNodes[currentIdx].children[0];
while (treeNodes[currentIdx].children[1] != 0) {
currentIdx = treeNodes[currentIdx].children[1];
}
}
return currentIdx;
}
void deleteValue(int valueToDelete) {
int foundNodeIdx = findNode(valueToDelete);
if (foundNodeIdx == 0) return; // Value not found
splay(foundNodeIdx, 0); // Bring the node to be deleted to the root
if (treeNodes[rootIndex].count > 1) { // If multiple occurrences, just decrement count
treeNodes[rootIndex].count--;
updateNodeSize(rootIndex);
return;
}
// If only one occurrence, delete the node
int leftSubtree = treeNodes[rootIndex].children[0];
int rightSubtree = treeNodes[rootIndex].children[1];
if (leftSubtree == 0 && rightSubtree == 0) { // No children
rootIndex = 0;
} else if (leftSubtree == 0) { // Only right child
rootIndex = rightSubtree;
treeNodes[rootIndex].parent = 0;
} else if (rightSubtree == 0) { // Only left child
rootIndex = leftSubtree;
treeNodes[rootIndex].parent = 0;
} else { // Both children exist
splay(leftSubtree, 0); // Splay the max of left subtree to be new root
linkNodes(rightSubtree, rootIndex, 1); // Attach right subtree to new root's right
updateNodeSize(rootIndex);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numOps;
std::cin >> numOps;
insertValue(-INF); // Sentinela para o menor valor
insertValue(INF); // Sentinela para o maior valor
for (int i = 0; i < numOps; ++i) {
int operationType, value;
std::cin >> operationType >> value;
if (operationType == 1) {
insertValue(value);
} else if (operationType == 2) {
deleteValue(value);
} else if (operationType == 3) {
std::cout << getRankOfValue(value) << "\n";
} else if (operationType == 4) {
std::cout << getValueByRank(value + 1) << "\n"; // +1 devido às sentinelas
} else if (operationType == 5) {
std::cout << treeNodes[findAdjacentNode(value, false)].value << "\n";
} else if (operationType == 6) {
std::cout << treeNodes[findAdjacentNode(value, true)].value << "\n";
}
}
return 0;
}
Árvore Splay para Manipulação de Sequências (Inversão de Intervalos)
Esta variante da árvore Splay é usada para gerenciar sequências e realizar operações como inversão de um subsegmento. Ela utiliza o lazyFlag para marcar e propagar operações de inversão.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::swap
const int INF = 0x3f3f3f3f; // Valor grande para sentinela
struct SplayNode {
int value;
int count; // Sempre 1 para sequências simples, a menos que se represente multi-conjuntos
int subtreeSize;
int parent;
int children[2]; // 0: esquerdo, 1: direito
int lazyFlag; // Usado para marcar inversões de intervalo
};
SplayNode treeNodes[1000101];
int rootIndex;
int nextFreeNodeIndex;
void updateNodeSize(int nodeIdx) {
treeNodes[nodeIdx].subtreeSize = treeNodes[treeNodes[nodeIdx].children[0]].subtreeSize +
treeNodes[treeNodes[nodeIdx].children[1]].subtreeSize +
treeNodes[nodeIdx].count;
}
bool isRightChild(int nodeIdx) {
return treeNodes[treeNodes[nodeIdx].parent].children[1] == nodeIdx;
}
void linkNodes(int childIdx, int parentIdx, int direction) {
treeNodes[parentIdx].children[direction] = childIdx;
if (childIdx != 0) {
treeNodes[childIdx].parent = parentIdx;
}
}
void pushLazyTag(int nodeIdx) {
if (treeNodes[nodeIdx].lazyFlag != 0) {
// Inverte os sinalizadores de lazy nos filhos
treeNodes[treeNodes[nodeIdx].children[0]].lazyFlag ^= 1;
treeNodes[treeNodes[nodeIdx].children[1]].lazyFlag ^= 1;
// Troca os filhos esquerdo e direito
std::swap(treeNodes[nodeIdx].children[0], treeNodes[nodeIdx].children[1]);
// Limpa o sinalizador no nó atual
treeNodes[nodeIdx].lazyFlag = 0;
}
}
void rotate(int nodeIdx) {
int parentIdx = treeNodes[nodeIdx].parent;
int grandParentIdx = treeNodes[parentIdx].parent;
bool isNodeRight = isRightChild(nodeIdx);
bool isParentRight = isRightChild(parentIdx);
linkNodes(treeNodes[nodeIdx].children[!isNodeRight], parentIdx, isNodeRight);
linkNodes(parentIdx, nodeIdx, !isNodeRight);
linkNodes(nodeIdx, grandParentIdx, isParentRight);
updateNodeSize(parentIdx);
updateNodeSize(nodeIdx);
}
void splay(int nodeIdx, int targetParentIdx) {
// Propaga tags do topo para baixo antes de qualquer rotação
// Cria um vetor de antepassados para propagar tags na ordem correta
std::vector<int> path;
int curr = nodeIdx;
while(curr != targetParentIdx) {
path.push_back(curr);
curr = treeNodes[curr].parent;
}
// Propaga de cima para baixo
for(int i = path.size() - 1; i >= 0; --i) {
pushLazyTag(path[i]);
}
while (treeNodes[nodeIdx].parent != targetParentIdx) {
int parentIdx = treeNodes[nodeIdx].parent;
int grandParentIdx = treeNodes[parentIdx].parent;
if (grandParentIdx != targetParentIdx) {
bool nodeIsRight = isRightChild(nodeIdx);
bool parentIsRight = isRightChild(parentIdx);
if (nodeIsRight == parentIsRight) { // Zig-Zig
rotate(parentIdx);
} else { // Zig-Zag
rotate(nodeIdx);
}
}
rotate(nodeIdx);
}
if (targetParentIdx == 0) {
rootIndex = nodeIdx;
}
}
void insertValue(int valueToInsert) {
int currentIdx = rootIndex;
int parentIdx = 0;
// Em sequências, geralmente inserimos no final ou em uma posição específica.
// Esta função insere um valor como em uma BST normal para construção inicial.
while (currentIdx != 0 && treeNodes[currentIdx].value != valueToInsert) {
parentIdx = currentIdx;
currentIdx = treeNodes[currentIdx].children[treeNodes[currentIdx].value < valueToInsert];
}
if (currentIdx != 0) { // Valor já existe, incrementa a contagem (ou ignora se for sequência única)
treeNodes[currentIdx].count++;
} else {
currentIdx = ++nextFreeNodeIndex;
if (parentIdx != 0) {
linkNodes(currentIdx, parentIdx, treeNodes[parentIdx].value < valueToInsert);
}
treeNodes[currentIdx] = {valueToInsert, 1, 1, parentIdx, {0, 0}, 0};
}
splay(currentIdx, 0);
}
// Retorna o índice do nó no k-ésimo rank (para sequências, equivale ao k-ésimo elemento)
int getNodeByRank(int rank) {
int currentIdx = rootIndex;
while (true) {
pushLazyTag(currentIdx); // Sempre propaga tags antes de decidir
int leftChildSize = treeNodes[treeNodes[currentIdx].children[0]].subtreeSize;
if (rank <= leftChildSize) {
currentIdx = treeNodes[currentIdx].children[0];
} else if (rank > leftChildSize + treeNodes[currentIdx].count) {
rank -= (leftChildSize + treeNodes[currentIdx].count);
currentIdx = treeNodes[currentIdx].children[1];
} else {
return currentIdx; // Retorna o índice do nó
}
}
}
// Imprime a sequência em ordem (travessia em-ordem)
void printSequence(int nodeIdx) {
if (nodeIdx == 0) return;
pushLazyTag(nodeIdx); // Propaga tags antes de visitar filhos
printSequence(treeNodes[nodeIdx].children[0]);
if (treeNodes[nodeIdx].value != -INF && treeNodes[nodeIdx].value != INF) {
std::cout << treeNodes[nodeIdx].value << " ";
}
printSequence(treeNodes[nodeIdx].children[1]);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numElements, numQueries;
std::cin >> numElements >> numQueries;
// Sentinelas para definir os limites da sequência
insertValue(-INF);
for (int i = 1; i <= numElements; ++i) {
insertValue(i);
}
insertValue(INF);
for (int i = 0; i < numQueries; ++i) {
int leftPos, rightPos;
std::cin >> leftPos >> rightPos;
// Para inverter o intervalo [leftPos, rightPos]:
// 1. O predecessor de leftPos (elemento em rank leftPos) é splayado para a raiz.
// 2. O sucessor de rightPos (elemento em rank rightPos + 2, devido às sentinelas)
// é splayado para ser o filho direito da raiz.
// 3. O subconjunto entre esses dois nós (filho esquerdo do sucessor) é o intervalo a ser invertido.
splay(getNodeByRank(leftPos), 0);
splay(getNodeByRank(rightPos + 2), rootIndex); // +2 por causa das 2 sentinelas
// O nó a ser invertido é o filho esquerdo do filho direito da raiz
int intervalRoot = treeNodes[treeNodes[rootIndex].children[1]].children[0];
treeNodes[intervalRoot].lazyFlag ^= 1; // Ativa a flag de inversão
}
printSequence(rootIndex);
std::cout << "\n";
return 0;
}