Уровень 8

Z-функция
Sqrt-декомпозиция, она же корневая эвристика
Sparse tables, двоичный подъем
Дерево отрезков
2-SAT
LCA (наименьший общий предок)