Cracking Conga Curse: Implicit Treap for Dynamic Sequence Operations

Hack The Box occasionally throws in coding challenges that feel closer to competitive programming than traditional exploitation. Conga Curse is one of them.

The challenge maintains a sequence of dancers, each with a vibe score, while repeatedly modifying their order. Some events reverse an entire range, others remove a dancer and reinsert them at another position, and queries ask for the dancer currently occupying a particular index.

At first glance, an array seems like the obvious representation. The problem is that reversing or moving elements in an array can require shifting a large portion of the sequence. With hundreds of thousands of dancers and operations, an \(O(N)\) update is far too expensive.

What we need is a data structure that treats the sequence itself as something we can efficiently split, rearrange, and join.

An implicit treap fits that model almost perfectly.

#The Problem

We are given:

• \(N\) dancers, each with an integer vibe score.
• \(M\) events operating on their current positions.

There are three event types:

F l r

Reverse the dancers at positions \(l\) through \(r\), inclusive.

Y i j

Remove the dancer currently at position \(i\) and insert them at position \(j\).

Q p

Retrieve the vibe score of the dancer currently at position \(p\).

Rather than printing every query result individually, the challenge asks for the sum of all values returned by Q operations.

The constraints are large:

A straightforward array implementation can require \(O(N)\) work for a reversal or move, leading to worst-case behavior on the order of \(O(NM)\).

We instead want each update to cost roughly:

#Why an Implicit Treap?

A regular binary search tree organizes nodes using explicit keys.

An implicit treap does something different: the position of a node in the sequence is determined implicitly by the sizes of its subtrees.

If a node has \(L\) elements in its left subtree, then that node occupies position:

within its subtree.

An in-order traversal therefore gives us the sequence in its current order.

Each node stores:

typedef struct Node {
    int val;
    uint64_t prio;
    int sz;
    int rev;
    struct Node *l, *r;
} Node;

The fields serve different purposes:

• val — the dancer's vibe score.
• prio — a random priority used to keep the treap balanced.
• sz — the number of nodes in the subtree.
• rev — a lazy flag indicating that the subtree should be reversed.
• l, r — left and right children.

Random priorities give the treap an expected height of:

which makes its fundamental operations efficient.

The real advantage, though, comes from two operations: split and merge.

#Split: Cutting the Sequence by Position

The operation:

split(root, k, &a, &b);

cuts a sequence after its first k elements.

Afterward:

• a contains positions 1 ... k
• b contains positions k + 1 ... N

For example:

Sequence:
A B C D E F

split(root, 3)

a = A B C
b = D E F

Because subtree sizes tell us how many elements lie to the left of a node, we can descend through the tree and find the split point in expected \(O(\log N)\) time.

void split(Node *t, int k, Node **a, Node **b) {
    if (!t) {
        *a = *b = NULL;
        return;
    }

    push(t);

    int left_sz = sz(t->l);

    if (k <= left_sz) {
        split(t->l, k, a, &t->l);
        *b = t;
        pull(t);
    } else {
        split(t->r, k - left_sz - 1, &t->r, b);
        *a = t;
        pull(t);
    }
}

Notice that push(t) happens before inspecting the subtree. That matters because a pending reversal may have swapped the logical meaning of the left and right children.

#Merge: Joining Two Sequences

merge(a, b) performs the opposite operation.

If every element in a should appear before every element in b, it joins them into one treap.

Conceptually:

a = A B C
b = D E F

merge(a, b)

A B C D E F

The tree with the larger root priority becomes the new root, and merging continues recursively down one side.

Node *merge(Node *a, Node *b) {
    if (!a)
        return b;

    if (!b)
        return a;

    if (a->prio > b->prio) {
        push(a);
        a->r = merge(a->r, b);
        pull(a);
        return a;
    } else {
        push(b);
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

Again, the expected cost is:

Split and merge are enough to express every modification required by the challenge.

#Lazy Range Reversal

Suppose we need to reverse:

[l, r]

Trying to physically rearrange every node in that range would defeat the purpose of using a tree.

Instead, we isolate the range using two splits:

root

→ a | [l ... r] | c

Then we toggle a lazy reversal flag on the middle subtree.

void reverse_range(Node **root, int l, int r) {
    Node *a, *b, *mid, *c;

    split(*root, l - 1, &a, &b);
    split(b, r - l + 1, &mid, &c);

    apply_rev(mid);

    *root = merge(merge(a, mid), c);
}

The important part is apply_rev():

static inline void apply_rev(Node *t) {
    if (!t)
        return;

    t->rev ^= 1;

    Node *tmp = t->l;
    t->l = t->r;
    t->r = tmp;
}

Reversing an entire subtree means:

1. Swap its left and right children.
2. Remember that its descendants also need to be interpreted in reverse order.

We do not immediately walk through every descendant.

Instead, push() propagates the flag only when we later need to descend into that subtree:

static inline void push(Node *t) {
    if (t && t->rev) {
        apply_rev(t->l);
        apply_rev(t->r);
        t->rev = 0;
    }
}

This is classic lazy propagation.

It turns what would normally be a linear-time range reversal into an expected:

operation.

#Moving a Dancer

The Y i j operation initially looks more complicated:

Remove the dancer at position i and insert them at position j.

One way to implement it is to split out the individual node and then insert it elsewhere.

There is an even cleaner way to think about it: moving one element is equivalent to rotating a contiguous range by one position.

#Moving Forward: i < j

Consider:

A B C D

Move A from position 1 to position 4:

B C D A

That is exactly a left rotation of the range:

[A B C D]

by one position.

So for i < j, we isolate [i, j], split off its first element, and append that element to the end:

[first | rest]

→

[rest | first]

The implementation is:

void rotate_left(Node **root, int l, int r) {
    if (l == r)
        return;

    Node *a, *b, *mid, *c;
    Node *first, *rest;

    split(*root, l - 1, &a, &b);
    split(b, r - l + 1, &mid, &c);

    split(mid, 1, &first, &rest);
    mid = merge(rest, first);

    *root = merge(merge(a, mid), c);
}

#Moving Backward: i > j

Now consider:

A B C D

Move D from position 4 to position 1:

D A B C

This is a right rotation of [1, 4].

We isolate the segment, split off its last element, and place that node in front:

[rest | last]

→

[last | rest]

void rotate_right(Node **root, int l, int r) {
    if (l == r)
        return;

    Node *a, *b, *mid, *c;
    Node *first, *last;

    int len = r - l + 1;

    split(*root, l - 1, &a, &b);
    split(b, len, &mid, &c);

    split(mid, len - 1, &first, &last);
    mid = merge(last, first);

    *root = merge(merge(a, mid), c);
}

The complete move operation becomes surprisingly small:

void move(Node **root, int i, int j) {
    if (i == j)
        return;

    if (i < j) {
        rotate_left(root, i, j);
    } else {
        rotate_right(root, j, i);
    }
}

This is one of the nicest parts of the solution: what sounds like an arbitrary erase-and-insert operation becomes a small number of standard treap splits and merges.

#Position Queries

For:

Q p

we need the node currently occupying position p.

At each node, let:

left_sz = sz(t->l);

Then:

• if p == left_sz + 1, the current node is the answer;
• if p <= left_sz, continue into the left subtree;
• otherwise, continue into the right subtree after adjusting the index.

int get(Node *t, int k) {
    push(t);

    int left_sz = sz(t->l);

    if (k == left_sz + 1) {
        return t->val;
    } else if (k <= left_sz) {
        return get(t->l, k);
    } else {
        return get(t->r, k - left_sz - 1);
    }
}

Because the treap remains balanced in expectation, the query also takes:

expected time.

Each result is added to the final answer:

answer += get(root, p);

#Keeping Subtree Sizes Correct

The implicit indexing only works if every node knows the current size of its subtree.

After modifying a child pointer, we recalculate:

static inline void pull(Node *t) {
    if (t)
        t->sz = 1 + sz(t->l) + sz(t->r);
}

This tiny function is fundamental.

Without accurate subtree sizes, positions would no longer correspond to in-order indices, and both split() and get() would become incorrect.

#Avoiding Allocation Overhead

The maximum number of dancers is known in advance, and nodes are never created or destroyed after initialization.

That makes a static node pool a natural fit:

static Node nodes[MAX_N + 5];
static int node_cnt = 0;

Creating a node becomes:

static inline Node *new_node(int val) {
    Node *n = &nodes[node_cnt++];

    n->val = val;
    n->prio = rng();
    n->sz = 1;
    n->rev = 0;
    n->l = n->r = NULL;

    return n;
}

This avoids hundreds of thousands of individual malloc() calls and gives predictable memory usage.

#Random Priorities

A treap combines two properties:

• sequence order is represented by in-order traversal;
• heap order is maintained using random priorities.

This implementation uses a fast SplitMix64-style generator:

static uint64_t rng_state = 0x9e3779b97f4a7c15ULL;

static inline uint64_t rng(void) {
    uint64_t z = (rng_state += 0x9e3779b97f4a7c15ULL);

    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
    z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;

    return z ^ (z >> 31);
}

We do not need cryptographic randomness here. The priorities only need to be distributed well enough to avoid consistently producing pathological tree shapes.

#Fast Input

The algorithm itself is efficient, but the challenge still processes hundreds of thousands of values and operations.

Using formatted input such as scanf() may be sufficient depending on the environment, but a buffered parser removes that variable entirely.

The implementation reads a large block with fread():

static char buf[1 << 20];
static int buf_idx = 0;
static int buf_size = 0;

and parses characters directly.

For performance-sensitive C challenges, this is a useful optimization once the algorithmic complexity is already under control.

#Complexity

Let \(N\) be the number of dancers and \(M\) the number of events.

A randomized treap has expected height:

Therefore:

With the straightforward initialization used below, the initial treap is built by repeatedly merging one node onto the end, giving an expected construction cost of \(O(N \log N)\).

The complete implementation therefore runs in:

expected time, with:

memory usage.

A linear-time Cartesian-tree construction could reduce initialization to \(O(N)\), but at these constraints it is unnecessary.

#Full C Implementation

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define MAX_N 240000

typedef struct Node {
    int val;
    uint64_t prio;
    int sz;
    int rev;
    struct Node *l, *r;
} Node;

static Node nodes[MAX_N + 5];
static int node_cnt = 0;

static uint64_t rng_state = 0x9e3779b97f4a7c15ULL;

static inline uint64_t rng(void) {
    uint64_t z = (rng_state += 0x9e3779b97f4a7c15ULL);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
    z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
    return z ^ (z >> 31);
}

static inline int sz(Node *t) {
    return t ? t->sz : 0;
}

static inline Node *new_node(int val) {
    Node *n = &nodes[node_cnt++];

    n->val = val;
    n->prio = rng();
    n->sz = 1;
    n->rev = 0;
    n->l = n->r = NULL;

    return n;
}

static inline void pull(Node *t) {
    if (t)
        t->sz = 1 + sz(t->l) + sz(t->r);
}

static inline void apply_rev(Node *t) {
    if (!t)
        return;

    t->rev ^= 1;

    Node *tmp = t->l;
    t->l = t->r;
    t->r = tmp;
}

static inline void push(Node *t) {
    if (t && t->rev) {
        apply_rev(t->l);
        apply_rev(t->r);
        t->rev = 0;
    }
}

Node *merge(Node *a, Node *b) {
    if (!a)
        return b;

    if (!b)
        return a;

    if (a->prio > b->prio) {
        push(a);
        a->r = merge(a->r, b);
        pull(a);
        return a;
    } else {
        push(b);
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

void split(Node *t, int k, Node **a, Node **b) {
    if (!t) {
        *a = *b = NULL;
        return;
    }

    push(t);

    int left_sz = sz(t->l);

    if (k <= left_sz) {
        split(t->l, k, a, &t->l);
        *b = t;
        pull(t);
    } else {
        split(t->r, k - left_sz - 1, &t->r, b);
        *a = t;
        pull(t);
    }
}

int get(Node *t, int k) {
    push(t);

    int left_sz = sz(t->l);

    if (k == left_sz + 1) {
        return t->val;
    } else if (k <= left_sz) {
        return get(t->l, k);
    } else {
        return get(t->r, k - left_sz - 1);
    }
}

void reverse_range(Node **root, int l, int r) {
    Node *a, *b, *mid, *c;

    split(*root, l - 1, &a, &b);
    split(b, r - l + 1, &mid, &c);

    apply_rev(mid);

    *root = merge(merge(a, mid), c);
}

void rotate_left(Node **root, int l, int r) {
    if (l == r)
        return;

    Node *a, *b, *mid, *c;
    Node *first, *rest;

    split(*root, l - 1, &a, &b);
    split(b, r - l + 1, &mid, &c);

    split(mid, 1, &first, &rest);
    mid = merge(rest, first);

    *root = merge(merge(a, mid), c);
}

void rotate_right(Node **root, int l, int r) {
    if (l == r)
        return;

    Node *a, *b, *mid, *c;
    Node *first, *last;

    int len = r - l + 1;

    split(*root, l - 1, &a, &b);
    split(b, len, &mid, &c);

    split(mid, len - 1, &first, &last);
    mid = merge(last, first);

    *root = merge(merge(a, mid), c);
}

void move(Node **root, int i, int j) {
    if (i == j)
        return;

    if (i < j) {
        rotate_left(root, i, j);
    } else {
        rotate_right(root, j, i);
    }
}

/* Fast input reader */

static char buf[1 << 20];
static int buf_idx = 0;
static int buf_size = 0;

static inline char getChar(void) {
    if (buf_idx >= buf_size) {
        buf_size = fread(buf, 1, sizeof(buf), stdin);
        buf_idx = 0;

        if (buf_size == 0)
            return 0;
    }

    return buf[buf_idx++];
}

static inline int nextInt(void) {
    char c;

    do {
        c = getChar();
    } while (c <= ' ' && c);

    int x = 0;

    while (c > ' ') {
        x = x * 10 + (c - '0');
        c = getChar();
    }

    return x;
}

static inline char nextOp(void) {
    char c;

    do {
        c = getChar();
    } while (c <= ' ' && c);

    return c;
}

int main(void) {
    int N = nextInt();
    int M = nextInt();

    Node *root = NULL;

    for (int i = 0; i < N; i++) {
        int val = nextInt();
        root = merge(root, new_node(val));
    }

    long long answer = 0;

    for (int i = 0; i < M; i++) {
        char op = nextOp();

        if (op == 'F') {
            int l = nextInt();
            int r = nextInt();

            reverse_range(&root, l, r);
        } else if (op == 'Y') {
            int i = nextInt();
            int j = nextInt();

            move(&root, i, j);
        } else if (op == 'Q') {
            int p = nextInt();

            answer += get(root, p);
        }
    }

    printf("%lld\n", answer);

    return 0;
}

#Takeaways

The interesting part of Conga Curse is not any one treap function. It is recognizing that the problem is fundamentally about manipulating a sequence through cuts and joins.

Once the sequence is represented as an implicit treap:

• reversing a range becomes split → toggle lazy flag → merge;
• moving a dancer becomes split → rotate a segment → merge;
• querying a position becomes a descent using subtree sizes.

That is the broader lesson worth remembering.

When a problem involves a large sequence with repeated operations such as cutting, inserting, moving, reversing, or querying by position, an implicit treap is often a much better mental model than an array.

Conga Curse looks like a simulation problem.

With the right data structure, it becomes a small collection of expected \(O(\log N)\) tree operations.