1) B с едука
curx = 0;
d = 1;
while (cur < n){
	curx += x;
	d++;
}

a1 + a2 + .. + an = (a1 + an) * n / 2


1 + 2 + 3 - 1 + 5 + 6 + 7 + ... + x >= n  

1) Втупую считаем сумма, пока она не будет больше n 
2) Если больше n на единицу - ответ + 1

#define int long long - все инты теперь являются лонгами, но можно все так же писать int x;

2) Префиксные суммы 

Нужно уметь быстро сумму элементов массива от l до r 

a[n] = a1, a2, ..., a_n-1


p[n] = a1, a1+a2, a1+a2+a3, ..., a1+a2+...+a_n-1

p[i] - сумма от 1 до i 

[l, r]
Сумма с l по r - p[r] - p[l - 1]

Так же часто надо сделать префиксный минимум или максимум 


p[i] = минимум с a1 до a_i

p[i] = min(a[i], p[i - 1]);

Узнать минимум на отрезке - это уже более сложно


3) 

bool cmp()
return a < b; - функция компаратора, можем передавать в библиотечную сортировку 

Продвинутые сортировки сравнением 


1)Быстрая сортировка:

quicksort

a[n] = a1, a2, ..., a_n-1 

1) Выберем любой элемент массива, a[k] 
2) Пихаем все элементы <=, в левую часть массива, а больше в правую часть массива 


Если выбирать элемент случайно - это работает в среднем за O(nlogn)

Давай выбирать средней элемент - a[(l + r) / 2]


Контртест:

2 4 6 8 1 5 3 7

2 4 6 7 1 5 3 

2 4 6 3 1 5 

2 4 5 3 1 

Наш алгоритм уже не работает за O(nlogn)
O(n^2)


4) Сортировка слиянием 

a[n] = a1, a2, .., a_n-1

1) Делим пополам
2) Сортируем половины 
3) Сливаем половины в посорченный массив 

1) У нас есть два массива, a[n], b[m] - они посорченны 

Оказывается, можно их слить в один за O(n + m), и он тоже будет посорчен 

c[n + m] = туда все записываем 

int left = 0, right = 0

int last_ind - последний пустой индекс в c = 0 изначально

a[left], b[right]

if (a[left] <= b[right]){
	c[last_ind] = a[left];
	last_ind++; left++;
}
else{
	c[last_ind] = b[right];
	last_ind++; right++;
}

1) sort(l, r)
m = (l + r) / 2;
sort(l, m); sort(m, r);
сливаем


Время работы 
На каждом этапе делим массив на 2 части, запускаем рекурсию и сливаем за O(n)

Оценим через дерево 
Высота дерева - logn
На каждом уровне - O(n)
O(nlogn)

Нельзя посортить быстрее, чем за O(nlogn)



Полезная штука - можем для каждого элемента хранить список индексов - его вхождений в массив

map < int, vector <int> > m;

for (i = 0; i < n; i++){
	m[a[i]].push_back(i);
}