DEMON: Contest Machinery
Optional and brutal. Contest machinery from Universal Cup, ICPC World Finals, and Chinese OI. No interviewer will ever ask you this.
-
Treaps, Splay & The Balanced BST Zoo
Splay trees, treaps, scapegoat trees, split and merge, implicit keys, Cartesian trees, and persistence.
-
Link/Cut Trees & The Dynamic Tree Family
Link/cut trees, Euler tour trees, fully dynamic connectivity, and offline deletion.
-
Wavelet Trees & Succinct Text Machinery
Wavelet trees, suffix automata, palindromic trees, linear-time suffix arrays, and persistent segment trees.
-
Heavy Query Machinery
Mo's algorithm, segment tree beats, kinetic segment trees, sqrt decomposition, CDQ, DSU on tree, and word parallelism.
-
DP Optimization Black Magic
Convex hull trick and Li Chao trees, Knuth and divide-and-conquer optimization, the Aliens trick, and SMAWK.
-
Flows, Matchings & Graph Structure Beyond Dinic
Unit-capacity Dinic, min cost flow, blossom matching, matroid intersection, dominator trees, chordal graphs, and virtual trees.
-
Polynomials, Moduli & Hashing Sorcery
NTT-friendly primes like 998244353, oversized convolutions, recovering linear recurrences, fast modular reduction, and hashes that survive anti-tests.