Specialized competition algorithms

Purpose

Specialized algorithms are for the most difficult problems. These are the tools that top programmers use in professional competitions. They solve problems that look impossible. They handle thousands of questions at once or find paths in very deep trees.

Why it exists

Standard tools are often too slow for these tasks. If you solve every question one by one, you will run out of time. These algorithms find a smarter way to organize the work so the computer does as little work as possible.

How it works

The system reorders your questions. It collects all your queries first. This is called offline processing. Then it sorts them so that moving from one question to the next takes very few steps. It also breaks large trees into smaller segments, making them easier to navigate.

Intuition

Think of it like a mail carrier. If a carrier delivers mail in the order they received it, they might drive across town for every letter. Instead, they sort the mail by street first. They move in one smooth line, saving time and energy.

Dependencies

Registry file: src/registry/categories/cp_specialized.ts. This is where the advanced logic is stored.
Target tools: Requires special libraries like bitset and cmath in C++ for maximum speed.

Implementation details

Sorting queries. The system uses a specific math curve to group questions that are close together.
Tree paths. For trees, it identifies the "heavy" paths and handles them as single lines to speed up the search.
Fast logic. It uses bit-level math to handle hundreds of true or false values at the same time.

Complexity

Tool	Pre-work	Step speed	Category
mo_algorithm	$O(Q \log Q)$	$O((N+Q)\sqrt{N})$ total	Offline
hld	$O(N)$	$O(\log^2 N)$	Tree
aho_corasick	$O(\sum	P	)$
bitset_accel	-	$O(N/64)$	Performance

Examples

Processing many range questions on an array:

ares
read arr as vector<int>
read queries as vector<Query>
use mo_algorithm on queries

Resulting C++ code:

cpp
int n = arr.size();
int BLOCK = (int)sqrt(n);
sort(queries.begin(), queries.end(), [&](auto &a, auto &b) {
    int block_a = a.l / BLOCK, block_b = b.l / BLOCK;
    if (block_a != block_b) return block_a < block_b;
    return (block_a & 1) ? a.r > b.r : a.r < b.r;
});

int curL = 0, curR = -1;
long long curAns = 0;
for (auto &q : queries) {
    while (curR < q.r) add(++curR);
    while (curL > q.l) add(--curL);
    while (curR > q.r) remove(curR--);
    while (curL < q.l) remove(curL++);
    ans[q.idx] = curAns;
}

Path questions on a tree:

ares
use hld on tree

Traces

This is what happens when you use a "rolling hash" to compare strings:

The system picks two special numbers to use for the math.
It creates a list of pre-calculated totals for your string.
It goes through the string and creates a unique number for every possible part.
When you want to compare two parts, it uses one math step to see if their numbers match.

Edge cases

Deep trees. For very large trees, the system uses specific loop patterns instead of recursive calls to keep the memory safe.
Small lists. If your list is very small, the system might skip the advanced sorting and solve the questions directly to save time.

Failure modes

Math collisions. In very rare cases, two different strings might result in the same number. You should use double checks if absolute safety is required.
Live questions. You cannot use these tools if your next question depends on the answer to your previous one.