1) Задача B с Div3 - изи подсчет

2) Фишки сортировки

2.1) Посортить в невозрастающем порядке - sort(a.rbegin(), a.rend())

2.2) Чтобы посортить на любом промежутке [start_it, final_it) : 

vector<int> :: iterator start_it = a.begin();
auto final_it = a.begin();
a = [1, 4, 2, 6, 8] - хотим посортить на [1, 4, 2]
int delta = n / 2 + 1;
advance(final_it, delta);
	
	либо же:
for (i = 0; i < delta; i++){
	final_it++;
}

sort(start_it, final_it);

2.3) Задача С с Div3 

Понятно, что нужно смотреть на вхождения элемента x, корректно обработать крайние случаи

Пусть мы выбрали элемент х, a = [..x, .., x..., x, ..] - за одну операцию удаляем все, что между 
соседними иксами

a = [x, ...]
a = [..., x] - если х встречается в массиве 1 раз и стоит в начале-конце, можно удалить все за 1 раз 

2.4) Как посортить массив + сохранить индексы:

vector<pair<int, int>> a(n);

for (i = 0; i < n; i++){
	cin >> a[i].first;
	a[i].second = i;
}

2.5)Как сортить по произвольному компаратару(компаратор - функция, которая принимает два элемента, и говорит, 
правда ли первый меньше второго)

sort(a.begin(), a.end(), comparator);

Например, по дефолту для сортировки пар используется такой:

bool comparatr(pair a, pair b){
	if (a.first < b.first){
		return a < b;
	}
	else if(a.first == b.first){
		return a.second < b.first;
	}
	return false;	
}

2.6) Немного про векторы 
	
Вектор - это массив, размер которого можно изменять 

vector<int> a;
a.push_back(4) - работает в среднем("амортизированно") за O(1)
a.pop_back() - аналогично

Условно говоря, все операции с векторами работают за константу
Амортизированная сложность - это значит, что суммарно за n операций мы сделаем O(n), но не значит, 
что каждая операция выполняется за O(1)

a.erase(it) - удаление по итератору из произвольной части массива работает за O(n)

В C++ есть lists - списки, это набор элементов, в каждом хранится ссылка на следующий

list<int> a;

a = [1] -> [4] -> [6] -> [7]

В списках можно удалять из произвольного места за О(1), мы просто перекидываем ссылку и очищаем память

a = [1] -> [4] -> [6] -> [7], делаем [1] -> [6] -> [7]

Но в списках нельзя обращаться по индексам

Мы платим возможностью удаления из любого места в массиве, но получаем индексацию


2.7)Поговорим про множества(структура, туда можно добавлять элементы, удалять, проверять наличие...)

Python:
set s - O(1) на любую операцию в среднем

C++:

set<int> s - 1 операция за O(logn), unordered_set<int> s - как в питоне


unordered_set = {1, 3, 6, 5}

set = {1, 3, 5, 7}

s = {}

set a = {1, 4, 5};//в set они лежат в отсортированном порядке
for (auto cur : a){//пройти по элементам set
		
}


Поэтому в программе из pdf мы делаем n операций по log, получаем O(nlogn)

2.8)Что такое логарифм?

log_x(y) - в какую степень надо возвести x, чтобы получить y 

log_2(16) = 4, т.к. 2^4 = 16

log_2(100000) ~ 19
log_2(1e9) ~ 30

log_2(a * b) = log_2(a) + log_2(b)

2.9) Как связаны логарифм и система счисления 

Мы привыкли думать в десятичной системе счисления(по понятным причинам).

Натуральное число можно представлять просто как сумму n единиц, 
единичная система счисления = 11..11(n единиц)

Но можно выбрать любое основание 

Система счисления с любым основанием: 

x_y - число х записано в системе счисления y

1000000000_10 = 1_1000000000

Система с основанием x

Есть цифры от 0 до x - 1

abc = a * x^2 + b * x^1 + c * x^0, abc - цифры от 0 до х - 1, по сути цифры - это просто натуральные числа, 
опять же, мы невольно думаем про них в десятичной системе 

Двоичная система:

Есть только 2 цифры, 0 либо 1, 1 цифра - это бит

7 = 0000000000000111 = 2^2 + 2^1 + 2^0 - можно добавлять сколько угодно единичек 


Логарифм - это количество единиц в двоичной записи числа 

Это следует из алгоритма перевода из десятичной системы в двоичную 

cin >> x;
vector<int> c;
while (x != 0){
	c.push_back(x % 2);
	x /= 2;
}
reverse(c);

Он работает, потому что число в 2 системе счисления можно представить в виде последовательности 
операций, прибавить единицу и умножить на 2(сдвинуть все символы на 1 влево), этот алгоритм - просто 
обратный порядок этой последовательности

2.10) Тип int в С++:

log_2(Max_int) = 32
int - [0, 1e9] - 32 бита 

int x = 7 = 00000000000000..00111(32 символа)

Пока что давай думать только про положительные числа(а так у нас просто бы был еще 1 бит на знак) 

2.10) Поразрядная сортировка: 


2.10.1) Сложность в общих словах: 

a = [1, 5, 4, 3, 7] - массив из int

O(n * logC) = O(n * 32) = O(n), но мы можем сортировать только целые числа, как и в случае сортировки 
подсчетом

2.10.2) Идея:
a = [1, 5, 4, 10, 9, 8] - массив из int 

a = [0001, 0101, 0100, 1010, 1001, 1000] - посмотрим на числа как на 4 битные числа(на еще 28 ведущих нулей
пока забьем)

Смотрим на старший бит, пихаем те числа, у которых там стоит 0 влево, остальные вправо 

a = [0001, 0101, 0100] - влево
a = [0001, 0100, 0101] - вправо 

2.10.3) Рекурсивная реализация:

a = [a1, a2, a3, ...]

Посортили по старшему биту и перешли в обе половины 

				[0.., 0.., 0.., .., 1.., 1..., 1..,]
				  ||                  ||
			[00.., .., 01...]      [10.., .., 11...]    
 			||             ||      ||             ||
			...           ...     ...             ...
			
Получается двоичное дерево рекурсии

Сложность = количество уровней(высота) * количество операций на каждом уровне

Всего logC уровней(32), так как смотрим по 1 разу на все биты 
На каждом уровне O(n) операций, просто раскидать числа влево-вправо  

Имеем O(nlogC)

O(log_10(С)) = O(log_2(С)) = O(logС) - по сути, нам пофиг на систему счисления, просто в двоичной 
удобно реализовывать, а ассимптотика - это просто про функции, а не про конкретные числа 
		

2.10.4) Почему это работает?

Пусть у нас n+1 битные числа 

1..0, 011..1, 16 = 8 + 4 + 2 + 1

Верна формула 2^n = 2^n-1 + ... + 2^0 + 1, поэтому 1 в старшем бите гарантирует, что число больше любого 
числа с 0 в этом бите(при условии, что это старший бит)

Как доказать? По индукции 
1 - верно 
2 = 1 + 1 - верно 
4 = 2 + 1 + 1- верно 
8 = 4 + 2 + 2 = 4 + 2 + 1 + 1 - верно
...
2^(n-1) = 2^(n-2) + 2^(n-3) + ... + 2^0 + 1 - предположим, что верно для всех n от 1 до n - 1, 
и умножим равенство на 2
2^n = 2^(n-1) + .. + 2^(n - 2) + .. 2^1 = 2^0 + 1 - доказано

2.10.5) Детали реализации:


Посмотреть на i-й бит:

x >> 3 - биты числа сдвигаются на 3 - побитовый сдвиг вправо на 3

if ((x >> i) % 2 == 1){
	там единица 
}
else{
	там 0
}


vector<int> sort(vector<int>a, num_bit){
	//Прописать частные случаи для выхода
	vector<int> l, r;
	//l - стоят нули в num_bit, r - единицы 
	for(i = 0; i < a.size(); i++){
		//раскидываем
	}
	l = sort(l, num_bit - 1);//сортим левую половину 
	r = sort(r, num_bit - 1);//сортим правую половину
	a = l + r;
	return a;
}

Сортировка слиянием - O(n * logn), поразрядная - O(n * logC), на некст занятии поговорим про слияние