\Section{Дерево отрезков}{26 февраля}{Винниченко Максим}

\Subsection{ДО сортированных массивов}
	
	\Subsubsection{Задача 1}

		Дана последовательность $a_1, a_2, \cdots, a_n$
		
		online Q запросов: $\langle L_j, R_j, x_j, y_j \rangle$ , посчитать число таких i, что  		
		
		$L_j \le i \le R_j, \   x_j \le a_i \le y_j$
		
		Замечаем что в ДО можно хранить произвольную структуру данных (Декартово дерево, Дерево отрезков, Sparse Table $\cdots$). 
		
		В нашем случае храним ДО сортированных массивов. Постоение за $\mathcal{O}(n \log n)$:
		во время built с
		
		Ответ на запрос: для всех вершинах ДО, затротронутых запросом делаем:
		\begin{lstlisting}
		$ans += upper_bound(all(T[v]), x_j) - lower_bound(all(T[v]), x);
		\end{lstlisting}
		$\mathcal{O}(n \log ^ 2 n)$
		
		К-порядковая статистика $\mathcal{O}(n \log ^ 3 n)$: бинарный по поиск ответу в задаче 1.
		
\Subsection{Scanline}	
	
	\Subsubsection{Задача 2}
	
	Offline.	

	Даны прямогольники.
	
	Q запросов посчитать, скольки прямоугольникам принадлежит точка.
	
	Разобьём запросы и прямоугольники на события:
		\begin{enumerate}
			\item Прибавить 1 на полосе. 
			\item Вычесть 1 на полосе.			
			\item Вычислить значение в точке.
		\end{enumerate}		
		
		Отсортируем события одной координате. Проходим по событиям в порядке сортировки. Запросы 1, 2 -- прибавть на отрезке, 3 -- посчитать сумму в точке.	
		
	\Subsubsection{Другое решение задачи 1}

		Offline.
		
		Геометрически задача 1 выглядит так: Q запросов посчитать число точек $\langle a_i, i\rangle$ на прямоугольнике.
		
		Разобьём запросы и точки на события:
		\begin{enumerate}
			\item Посчитать сумму на полосе, и добавить к ответу на запрос. 
			\item Посчитать сумму на полосе, и вычесть из ответа на запрос.			
			\item Прибавить 1 в точке.
		\end{enumerate}		
		
		Отсортируем события одной координате. Проходим по событиям в порядке сортировки. Запросы 1, 2 -- посчитать сумму на отрезке, 3 -- прибавить в точке.		
		
		Online:
			оставим только события типа 3, сделаем scanline персистеным.
			
		Уже умеем задачу 1 за $\mathcal{O}(n \log n)\ $ $\Longrightarrow$ K-порядковую статистику на отрезке научились искать за $\mathcal{O}(n \log ^ 2 n)$.
		
\Subsection{К-порядковая статистика за $\mathcal{O}(n \log n)$}

	Избавимся в решении за $\mathcal{O}(n \log^2 n)$ от бинарного поиска с помощью параллельного спуска. Обратитмся к версия соответствующим l - 1 и r и будем параллельно в их спускаться аналогично поиску K-ой единицы с помощью ДО.
	
	\begin{lstlisting}
    int get(int v1, int v2, int tl, int tr, int k) {
        int tm = (tl + tr) / 2;
        if (tr - tl <= 1) return tl;
        int lCnt = T[T[v2].l].cnt - T[T[v1].l].cnt;
        if (lCnt > k) {
            return get(T[v1].l, T[v2].l, tl, tm, k);
        } else {
            return get(T[v1].r, T[v2].r, tm, tr, k - lCnt);
        }
    }
	\end{lstlisting}
	
	
	
	