\Section{Простые алгоритмы}{2 октября}{Азанов Михаил}
\Subsection{Вектор -- расширение и сужение.}
\begin{enumerate}
\item	 Две основных характеристики вектора - size и capacity. size обозначает количество элементов в векторе, а capacity - количество выделенных ячеек памяти. Для того, чтобы не занимать много памяти и быстро работать при этом, методы PUSH и POP в векторе устроены интересным образом.
	 
	PUSH:
	\begin{code}
		if (size == capacity) {
			capacity *= 2;
		}	
	\end{code}
	POP:
	\begin{code}
		if (size == capacity / 4) {
			capacity /= 2;
		}
	\end{code}

\item	Докажем, что эти методы работают за амортизированное $\mathcal{O}(1)$, найдем потенциал $\varphi$, который удовлетворяет следующим свойствам:
	\begin{enumerate}
		\item $a_i = t_i + \Delta{\varphi}$
		\item \ $\begin{cases}
					\varphi_0 = 0  \\
					\varphi_i \ge 0 
			  \end{cases}$
		\item PUSH : $\Delta\varphi =  \begin{cases}
											+2\\
											-capacity \ [= size]
										\end{cases}$
		\item POP : $\Delta\varphi =  \begin{cases}
											+4\\
											-capacity \ [= 4size]
									   \end{cases}$
	\end{enumerate}
	Рассмотрим функцию $\varphi$, которая будет меняться вышеописанным образом и возьмем её в качестве потенциала. Нетрудно заметить, что сохраняется условие $\varphi>0$.
	\item \begin{Thm}
		Операции POP и PUSH работают в среднем за $\mathcal{O}(1)$.
		
		\THEE{Доказательство.}\\
		\ \ \ $\sum a_i  = \sum t_i + \Delta\varphi$\\
		Заметим, что $\Delta\varphi = \varphi_{last} - \varphi_0 = (\ge 0) - 0 \ge 0$\\
		Таким образом, получаем $\sum a_i \ge \sum t_i$\\
		Тогда $a_i = \mathcal{O}(1) \Rightarrow \frac{\sum t_i}{n} = \mathcal{O}(1)$, что и требовалось доказать.
		\end{Thm}
	
\end{enumerate}
	
\Subsection{Два указателя.}

	 Задача: находить количество различных чисел на отрезке [L, R] оффлайн за $\mathcal{O}(n\sqrt{m})$, $m$ - количество запросов.
		\begin{enumerate}
			\item Предположим сначала, что запросы отличаются не сильно. Научимся обрабатывать запросы за $\mathcal{O}(1)$.
			
			L$++$, L$--$, R$++$, R$--$:
			
			Используем HashMap, $x \rightarrow count[x]$.
			
			\item Пусть теперь L$_i$ $\le$ L$_{i+1}$ и R$_i$ $\le$ R$_{i+1}$. Научимся обрабатывать запрос за $\mathcal{O}(n + M)$.
			
			Храним 2 указателя L, R. При переходе к следующему отрезку применяем сколько надо раз пункт (a). Заметим, что указатели сдвинулись максимум на $n$. Отсюда оценка на $\mathcal{O}(n+M)$.
			
			\item Теперь L и R всегда произвольные.
			
			Идея: Разделим все запросы на группы где L$_i$ лежит в отрезках $[1,k], [(k+1),2k], \ldots$. В каждой группе упорядочим запросы по R.
			
			Заметим, что когда мы разбираемся с какой-то группой, R пробегает не более $n$, а L не более $k m_i$, где $m_i$ - количество запросов в $i$-й группе. Итого получаем $\mathcal{O}(n + k m_i)$ на группу.
			
			Осталось просуммировать по $i$. Получаем $\mathcal{O}(n\frac{n}{k} + kM)$.
			
			Чтобы минимизировать ответ, надо взять такое $k$, что $n\frac{n}{k} = kM \Rightarrow k = \sqrt{\frac{n^2}{M}} = \frac{n}{\sqrt{M}}$.
			
			Подставляя, получаем ответ $\mathcal{O}(n\sqrt{M})\ [+sort = \mathcal{O}(n+M)]$
			
			
	\end{enumerate}
	
\Subsection{k-я порядковая статистика.}
	Задача: по данному числу $k$ находить $k$-й элемент в отсортированном массиве за $\mathcal{O}(n)$. Изначально массив не отсортирован.
	
	\begin{enumerate}
		\item Сразу напишем псевдокод функции.
		
		\begin{code}
			KStat (a, L, R, k) {
				x = a[*]
				partition(x)
				if (k < M1)
					KStat(a, L, M1 - 1, k)
				if (k > M2)
					KStat(a, M2 + 1, R, k)
			}
		\end{code}
		
		\item Будем искать * следующим образом: Поделим массив на подмассивы длины 5.Если $n$ не делится на 5, заполним до делящегося произвольными элементами массива. Отсортируем подмассивы и рассмотрим массив их медиан. Его медиана, найденная применением рекурсивно этого алгоритма, и будет *.
		$n < 5$ - база рекурсии, перебираем руками.
		
		Заметим, подмассивов у нас $n/5$, а среди них таких, что их медиана меньше *, следовательно, $n/10$. Тогда элементов в исходном массиве, меньших * хотя бы $n/10 * 3$. Хотя бы столько же и элементов больших *. Следовательно, рекурсивно (после partition(x)) алгоритм получит максимум $7n/10$ элементов.
		
		\item $T(n) \le T(n/5) + T(7n/10) + n = \Theta(n).$
		
		Если рассмотреть дерево рекурсии, то на каждом уровне сумма коэффициентов рекурсивных вызовов не больше чем $(n/5 + 7n/10 < 1) \cdot a$, где $a$ - сумма на предыдущем уровне. Получаем ограничение сверху как сумму геометрической прогрессии с коэффициентов меньше единицы. Значит, ответ $\Theta(n)$.
		
	\end{enumerate}
	
	
	
	
	
	
	
	
	
	
	
	
	