Привет. Есть задача, дано список целых чисел, для каждого пара последовательных

элементов найти ответ на : встречал ли это пара ранее (то есть до этих пар если обрабатываем элементов с начала список до конца). значение чисел от 1 до 100 000 .

Можно это реализовать без предварительно сортироват пара элементов?

За O(log(n)) для каждого поиска? Хотел использовать heap data structure, но оказывается там удаление/добавление O(log(n)) , но поиск O(n) в худшем случай.

Хэш таблица — не хочу, потому что реализую в Си, там не хочу реализовать хэш таблицу).

А что за пар элементов? Это что за газ такой?

В дерево клади

O2 кислород.

segment tree ? но там (x,y) пара как кладу?

Binary tree

А в чём проблема отсортировать? Сложность же будет такая же

Не умею реализовать quick sort in C ), там есть свои грабли, если меньше 16 элементов нужен insertion sort, иначе по рекурсия идти... Или наоборот если глубина рекурсия больше лимит=10 или 15, нужен insertion sort, точно не помню что-то было

Он в библиотеке готовый есть см. qsort

А он гарантирует O(n logn)?

Стандарт не гарантирует, но приличные имплементации обычно гарантируют

Не гарантирует, ибо qsort это амортизированная n*log(n), но фактически вероятность получить вырожденный случай n^2 сверх мала.

Стандарт c++ гарантирует O(n logn) для std::sort в худшем случай. Но но есть история libc++ до 14 версий это сломано))