\documentclass[12pt]{article}

% Автор: Сергей Копелиович

\usepackage{polyglossia}

%\usepackage{amsthm, amsmath, amssymb}
\usepackage{amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{enumerate}
\usepackage{hologo}
\usepackage{minted}
\usepackage{unicode-math}
\usepackage{lastpage}

\defaultfontfeatures{Ligatures=TeX}
\setmainfont{CMU Serif}  
\setmonofont{CMU Typewriter Text}  
\setsansfont[Mapping=tex-text]{CMU Sans Serif}
\setmathfont{Latin Modern Math}
\setdefaultlanguage[spelling=modern]{russian}
\setotherlanguage{english}

\sloppy

\voffset=-20mm
\textheight=220mm
\hoffset=-25mm
\textwidth=180mm

\def\EPS{\varepsilon}
\def\SO{\Rightarrow}
\def\EQ{\Leftrightarrow}
\def\t{\texttt}
\def\O{\mathcal{O}}
\newcommand{\q}[1]{\langle #1 \rangle} % <x>
\newcommand\URL[1]{{\footnotesize{\url{#1}}}}
\def\myindent{\hspace*{\parindent}}
\def\up{\vspace*{-\baselineskip}}
\def\NO{\t{\#}}
\newcommand{\ITEM}[1]{{\bf \underline{#1}}\hspace{0.5em}}

\makeatletter

\renewcommand{\@oddfoot}{
    \parbox{\textwidth}{
        %\hrule
        %\vspace{6pt}
        \sffamily
        {{\hfil}\thepage/\pageref*{LastPage} \hfil}%
    }
}

\newenvironment{MyList}{
  \begin{enumerate}
  \setlength{\parskip}{-5pt}
  \setlength{\itemsep}{5pt}
}{
  \end{enumerate}
}

\begin{document}

\begin{center}
  {\Large \bf MIPT, сборы 2014, день \NO{3}} \\ 
  \vspace{0.5em}
  {\Large \bf Тема: структуры данных \\ \vspace{0.2em} корневая оптимизация, пересечение полуплокостей} \\
  \vspace{0.5em}
  {\large 14 ноября, Сергей Копелиович} \\
  %\vspace{0.5em}
  %{Собрано {\today} в {\currenttime}}
\end{center}

\vspace{-1em}
\noindent \underline{\hbox to 1\textwidth{{ } \hfil{ } \hfil{ } }}

\section{Корневая оптимизация}
              
\myindent{}Рассмотрим задачу про поиск подстрок $s_1, s_2, \dots, s_k$ одинаковой длины $l$ в строке $t$.
Для каждого $i$ нужно узнать, встречается ли $s_i$ в $t$, как подстрока.
Мы умеем решать такую задачу за линейное время, точнее говоря, за $\O(lk+|t|)$ с помощью хеш-таблицы полиномиальных хешей строк $s$.
Здесь вы можете правильно заметить, что подобные задачи следует решать алгоритмом Ахо-Корасик,
но давайте ненадолго представим, что мы его не знаем, зато про хеши уже слышали.

Пусть теперь даны строки произвольных длин. Как для новой задачи использовать наше решение с хешами? Идея корневой оптимизации в том, что
если суммарная длина всех строк равна $L$, то строки длины до $\sqrt{L}$ мы можем перебрать за $\O(L + |t|\sqrt{L})$,
а строк длины больше $\sqrt{L}$ всего лишь $\O(\sqrt{L})$, поэтому суммарное время работы решения ``сгруппируем строки по длине, 
и для каждой длины решим за линейное время'' получается также $\O(L + |t|\sqrt{L})$.

Такую идею можно использовать не только для строковых задач, но и, например, для задач про деревья.
В дереве из $n$ вершин может быть много вершин степени не более $\sqrt{n}$, а вершин степени хотя бы $\sqrt{n}$ не более $\sqrt{n}$.

\section{Корневая оптимизация на массиве}

\myindent{}Рассмотрим абстрактную задачу ``у нас есть массив $a$, и мы хотим делать с ним много разных сложных запросов на отрезках''.
Начнем с простого. Запрос \NO{1}: сумма на отрезке. Запрос \NO{2}: поменять значение в точке.
Будем за $[f(n), g(n)]$ обозначать то, что некая структура данных на запросы первого типа умеет отвечать за $f(n)$, а на запросы второго типа за $g(n)$.
Наша задача решается деревьями отрезков и Фенвика за время $[\O(\log n), \O(\log n)]$.
Мы сейчас решим ее за время $[\O(1), \O(\sqrt{n})]$ и за время $[\O(\sqrt{n}), \O(1)]$.
Обозначим $k = \lfloor\sqrt{n}\rfloor$. 

\vspace{0.5em}
Решение \NO{0}. Заметим, что мы можем насчитать суммы на префиксах (частичные суммы) исходного массива \t{sum[i+1]=sum[i]+a[i]}, 
сумма на отрезке $[l,r]$ тогда равна \t{sum[r+1]-sum[l]}, а при каждом изменении массива будем пересчитывать весь массив \t{sum}.
Кроме того мы можем ничего дополнительного не хранить, и сумму искать за линейное время.
Это решения за $[\O(n), \O(1)]$ и $[\O(1), \O(n)]$ соответственно. 

\vspace{0.5em}
Решение \NO{1} за $[\O(k), \O(1)]$. Будем поддерживать массив $s$, $s[i]$ равно сумме $a[j]$ по $j \in [ki..k(i+1))$. 
Запрос ``сумма на отрезке'': отрезок разбивается на ``хвосты'' и $\O(k)$ кусков с уже известной суммой. 
Запрос ``поменять значение в точке'': \\
\t{set(i,x) \{ s[i/k] += x-a[i]; a[i] = x; \}} 

\vspace{0.5em}
Решение \NO{2} за $[\O(1), \O(k)]$. Поддерживаем тот же массив $s$, а также частичные суммы массива $s$.
Кроме того на каждом отрезке $[ki..k(i+1))$ насчитаем частичные суммы.
Чтобы сделать изменение в точке, нужно целиком пересчитать два массива частичных сумм (суммы конкретного куска, суммы на $s$).
Чтобы узнать сумму на отрезке, достаточно разбить его на два ``хвоста'' и все остальное. На каждой из трех частей мы умеем считать сумму за $\O(1)$.

\vspace{0.5em}
Решение \NO{3} за $[\O(k), \O(k)]$. Будем поддерживать суммы на префиксах \\
\t{sum[i+1]=sum[i]+a[i]} и массив изменений,
произошедших с массивом с тех пор, как мы считали суммы на префиксах, -- $changes$. Одно изменение --
пара $\q{i,x}$, обозначающая операцию \t{a[i]+=x}.
Будем поддерживать свойство $|changes| \le k$.
Запрос ``сумма на отрезке'': сумма на отрезке $[l,r]$ в исходном массиве была равна \t{sum[r+1]-sum[l]},
за $\O(|changes|)$ мы можем посчитать, насколько она с тех пор изменилась.
Запрос ``поменять значение в точке'': чтобы в точку $i$ записать новое значение $x$, добавляем в $changes$ пару $\q{i,x-a[i]}$, в $a[i]$ записываем $x$.
Если после этого $|changes| > k$, за $\O(n)$ строим суммы на префиксах текущего массива $a$ и очищаем список $changes$.
Эту операцию назовем \t{rebuild}. Заметим, что \t{rebuild} мы будем вызывать не чаще, чем один раз за $k$ запросов, поэтому
амортизированное время обработки одного запроса равно $\O(\frac{n}{k}) = \O(\sqrt{n})$.

\vspace{0.5em}
Последнюю технику будем называть ``отложенные операции''.
Для данной задачи такая техника не имеет никаких плюсов, но пригодится нам в дальнейшем.

\section{Корневая оптимизация на массиве: split \& rebuild}

Решим теперь более сложную задачу: операции с массивом будем делать такие 
\begin{MyList}
  \item \t{Insert(i, x)} -- вставить $x$ на позицию $i$.
  \item \t{Erase(i)}     -- удалить $i$-й элемент массива.
  \item \t{Sum(l,r,x)}   -- посчитать на отрезке $[l,r]$ сумму элементов больших $x$.
  \item \t{Reverse(l,r)} -- перевернуть отрезок $[l,r]$.
\end{MyList}
Чтобы решить такую задачу, для начала научимся отвечать на запрос \t{Sum(l,r,x)} (единственный запрос с осмысленным ответом),
применный ко всему массиву, то есть на запрос \t{Sum(0,n-1,x)}. Пусть пока других типов запросов нет, есть только один запрос \t{Sum}.
Тогда достаточно поддерживать отсортированную версию исходного массива и частиные суммы на ней.
Ответ на запрос -- бинарный поиск по массиву и обращение к частичным суммам. Время построения
структуры данных $\O(n \log n)$, время ответа на один запрос $\O(\log n)$.

Теперь решим полную версию задачи.
Есть массив $a[0..n)$.
Будем также в каждый момент времени хранить разбиение массива на отрезки $T = [A_1, A_2, \dots, A_m]$.
Для каждого отрезка у нас будут храниться две версии -- исходная и отсортированная с частичными суммами.
Постараемся поддерживать два свойства: $\forall i \colon |A_i| \le \sqrt{n}$ и $m < 3\sqrt{n}$.
Изначально разобьем массив на $k = \sqrt{n}$ отрезков длины $\sqrt{n}$.
Для каждого из $k$ отрезков за $\sqrt{n}\log n$ вызовем операцию \t{build}, которая построит отсортированный массив и частичные суммы.
Теперь напишем основную операцию \t{split(i)}, которая возвращает такое $j$, что $i$-й элемент -- начало $j$-го отрезка.
Если точка $i$ не является началом ни одного из отрезков, найдем такой $A_j = [l,r)$, что $l < i < r$,
и разобьем его на два отрезка $B = [l,i)$ и $C = [i,r)$. Для отрезков $B$ и $C$ запустим \t{build}, 
получим новое разбиение массива на отрезки: $T' = [A_1, A_2, \dots, A_{j-1}, B, C, A_{j+1}, \dots, A_m]$.
Время работы операции \t{split(i)} равно $\O(k) + \O(\t{build}(\frac{n}{k}))$, то есть при $k = \sqrt{n}$ получается $\sqrt{n}\log n$.
Здесь мы пользуемся тем, что внутри $T$ хранятся не сами отрезки, а ссылки на них, поэтому ``копирование'' отрезков происходит за $\O(1)$.
Теперь у нас получится через \t{split(i)} просто выразить все остальные операции.
\begin{minted}{c}
  vector<Segment*> T;
  int split( int i ) { ... }
  void Insert(i, x) {
    a[n++] = x;
    int j = split(i);
    T.insert(T.begin() + j, new Segment(n-1, n));
  }
  void Erase(i) {
    int j = split(i);
    split(i + 1);
    T.erase(T.begin() + j);
  }
  int Sum(l, r, x) { // [l, r]
    l = split(l), r = split(r + 1); // [l, r)
    int res = 0;
    while (l <= r)
      res += T[l++].get(x); // бинарный поиск и обращение к частичным суммам
    return res;
  }
\end{minted}
Чтобы обрабатывать запросы типа \t{Reverse}, нам нужно для каждого отрезка хранить дополнительный флаг ``развернут ли отрезок'',
код операции \t{split(i)} несколько усложнится, остальная часть не изменится.
\begin{minted}{c}
  void Reverse(l, r) { 
    l = split(l), r = split(r + 1);
    reverse(T + l, T + r)
    while (l <= r)
      T[l++].reversed ^= 1;
  }
\end{minted}
Сейчас у нас есть решение, которое начинает с $k = \sqrt{n}$ отрезков, и выполнение каждого запроса увеличивает $k$ не более чем на $2$. 
Через $k$ запросов может произойти ситуация, что $k \ge 3\sqrt{n}$ (стало в три раза больше), в этот момент мы за $\O(n \log n)$ перестроим
всю структуру (сделаем \t{rebuild}). Амортизированное время выполнение операции \t{rebuild} равно $\frac{n \log n}{k} = \sqrt{n}\log n$.
Итого наше решение обрабатывает все запросы за амортизированное время $\O(\sqrt{n}\log n)$.

Можно ускорить. Для этого заметим, что \t{split(i)} можно делать за линейное время, то есть за $\O(k+\frac{n}{k})$, 
а операцию \t{rebuild} можно делать за время $\O(n)$.
Тогда если выбрать количество отрезков $k$ равным не $\sqrt{n}$, а $\sqrt{n /\log n}$, 
амортизированное время ответа на один запрос типа \t{Sum} будет $\O(S + G + R)$, где
$S$ -- время \t{split(i)}, равно $\O(\frac{n}{k}+k)$,
$G$ -- время внутреннего цикла функции \t{Sum}, равно $\O(k\log n)$, 
$B$ -- амортизированное время на один \t{rebuild}, равно $\O(\frac{n}{k})$.
Получаем в сумме $\O(\sqrt{nlogn})$ на запрос.
             
\section{Пересечение полуплоскостей}

\myindent{}Решим одну сложную задачу \href{http://acm.timus.ru/problem.aspx?space=1&num=1390}{acm.timus.ru:1390}.
Условие такое: мы стоим на плоскости в точке $(0,0)$. Время от времени на плоскости появляются
стенки -- отрезки, не проходящие через $(0,0)$. Стенки могут пересекаться.
Время от времени мы выпускаем в произвольных направлениях пули. Пуля летит по прямой, пока не каснется стены. 
Ответ на запрос типа ``пуля'' -- расстояние, которое она пролетит (возможно, бесконечность).

В итоге мы научимся $n$ запросов произвольного вида обрабатывать за время $\O(n \log^2n)$.
Но для начала попробуем понять, как вообще подступиться к задаче.
Задача сложная. Запросы разных типов вперемешку, стены пересекаются...
Попробуем задачу упростить. Пусть уже какие-то стены есть, а новые не появляются, более того, пусть все стены -- прямые.

{\bf Задача теперь имеет следующий вид:}
даны прямые, которые высекают на плоскости выпуклый многоугольник, содержащий точку $(0,0)$, нужно
уместь быстро по лучу из точки $(0,0)$ находить точку пересечения с границей многоугольника.
Решение задачи: пересечем полуплоскости за $\O(n \log n)$, получим многоугольник. Затем каждый запрос мы обработаем бинарным
поиском за время $\O(\log n)$. Обсудим решение подробнее, начнем с бинарного поиска.
Возьмем угол $\alpha$ любой из вершин многоугольника. 
Для каждой другой вершины возьмем ее угол из промежутка $[\alpha, \alpha+2\pi)$, выпишем эти числа в возрастающем порядке, получим массив углов $a$.
Чтобы понять, куда попадет пуля, пущенная в направлении $(x,y)$, посчитаем угол $\beta \in [\alpha, \alpha+2\pi)$, найдем бинарным поиском
минимальное $i \colon a[i] \le \beta < a[i + 1]$ и пересечем отрезок, образованный точками $i$, $i+1$ с лучом, по которому летит пуля. Время $\O(\log n)$.
Теперь пересечение полуплоскостей. Во-первых, чтобы они точно в пересечении давали конечный многоугольник, добавим bounding box, полуплоскости
$-M \le x, x \le M, -M \le y, y \le M$, где $M$ выбирается из ограничений на координаты исходных точек.
Теперь отсортируем все прямые по углу нормали (угол от $0$ до $2\pi$). Из прямых с одинаковым углом оставим лишь ту, что ближе к $(0,0)$.
Затем будем добавлять прямые в таком порядке в стек. Перед добавлением очередной прямой, несколько верхних прямых со стека нужно снять.
Пусть сейчас верхние прямые на стеке -- $l_1$, $l_2$.
Верхнюю прямую нужно снять со стека, если точка $p = intersect(l_1, l_2)$ лежит по другую сторону чем $(0,0)$ от новой прямой.
В стеке наращивается многоугольник-ответ. Чтобы многоугольник замкнулся в цикл, добавим второй раз все прямые в таком же порядке.
Теперь содержимое стека = хвост + ответ + хвост. Чтобы отрезать хвосты, рассмотрим точки пересечения соседних прямых на стеке и
возьмем ту, которая встречается два раза. Между этими двумя позициями в стеке лежит многоугольник-ответ.
Время построения $\O(sort) + \O(n)$.

{\bf Усложним задачу:} пусть теперь прямые добавляются.
Можно применить технику отложенных операций и обрабатывать каждый запрос типа ``пуля'' за $O(\sqrt{n})$.
Как только отложенных добавлений прямых станет больше чем $\sqrt{n}$, вызываем процедуру \t{rebuild}, которая
отработает за $\O(n)$, так как старые прямые уже отсортированы, а новые $\sqrt{n}$ штук мы можем
примерджить за $\O(\sqrt{n}\log n + n)$. Итого, время обработки $n$ запросов будет $\O(n\sqrt{n})$. 

Можно поступить по-другому и хранить вершины многоугольника не в отсортированном по углу массиве, а в сбалансированном 
дереве поиска. Тогда, чтобы добавить новую прямую с направляющим вектором $\vec{v}$ и нормалью $\vec{n}$ (направление от $(0,0)$), нужно 
научиться находить вершину многоугольника $\vec{p} \colon$ скалярное произведение $\q{\vec{n}, \vec{p}}$ максимально.
Это можно сделать бинарным поиском по сортированному массиву. Или, теперь у нас дерево поиска, спуском вниз по дереву поиска.
Если точка $\vec{p}$ лежит, с той же стороны от прямой, что и $(0, 0)$, ничего делать не нужно, иначе
нужно удалить $\vec{p}$ и, возможно, еще несколько смежных с ней вершин многоугольника. Вместо них добавятся две точки.
Удалять будем в цикле, пока очередная точка не будет с той же стороны, что и $(0, 0)$ от прямой. В конце добавим точку пересечения стороны и отрезка,
на котором мы остановили процесс удаления. Время добавления новой прямой получилось $\O(\log n + k \log n)$, где $k$ -- количество удаленных точек.
Каждая точка удалится только один раз, поэтому суммарное время обработки $n$ запросов -- $\O(n \log n)$.
С точки зрения скорости работы предыдущее решение гораздо хуже. С точки зрения простоты реализации предыдущее
решение в разы проще.

{\bf И еще раз усложним задачу:}
теперь у нас не прямые, а отрезки. Сперва решим задачу в offline (все запросы известны заранее).
Тогда мы знаем множество всех возможных углов точек концов отрезков. Отсортируем их и построим на массиве углов дерево отрезков.
Каждой вершине дерева отрезков соответствует некоторый диапазон углов.
Когда мы добавляем стену, деревом отрезков она разбивается на $\O(\log n)$ вершин дерева отрезков,
в каждой из которых стена идет ровно от левой границы диапазона углов до правой, то есть ведет себя как прямая.
Итого: в каждой вершине дерева отрезков поддерживаем пересечение полуплоскостей.
Заметим, чтобы построить пересечение полуплоскостей внутри вершины дерева отрезков, нужно строить не многоугольник (замкнутую ломаную),
а ломаную от левого луча до правого (можно считать, что разница углов не более $\frac{\pi}{4}$).
Поэтому процедура построения пересечения полуплоскостей значительно упрощается -- достаточно одного прохода со стеком, каждую
прямую добавить один раз. По второму разу добавлять прямые, а затем выделять цикл не нужно.
Итак, у нас есть дерево отрезков, в каждой вершине которого лежит пересечение полуплоскостей.
Обработка запроса ``пуля'': угол пули попал в $\log n$ вершин дерева отрезков, в каждой из этих вершин
сделаем за $\O(\log n)$ запрос к структуре на полуплоскостях. Суммарное время работы $\O(\log^2 n)$.
Обработка запроса ``добавить стену'': разбили ее на $\log n$ вершин дерева отрезков и в каждую вершину
добавили ``прямую'' в структуру полуплоскостей. Суммарное время работы $\O(\log^2 n)$.
Используемая память -- $O(n \log n)$.

Теперь, чтобы получить решение в online, достаточно от обычного дерева отрезков
перейти к динамическому. Изначально дерево отрезков содержит только корень.
Затем по ходу запроса к дереву отрезков, если мы пытаемся пойти в не существующую вершину, создаем ее.
Процесс спуска вниз по дереву отрезков останавивается, когда длина отрезка меньше $\EPS$.

Можно было тоже самое сделать, используя отложенные операции, тогда время обработки запроса было бы $\O(k + \log^2n)$.
Где $k$ -- количество отложенных операций. Структуру мы строим за время $\O(n \log n)$ -- один раз отсортировали стены-прямые,
затем в каждой вершине дерева отрезков за линейное время построили пересечение соответствующих полуплоскостей.
Оптимально максимальное $k$ выбрать равным $\sqrt{n \log n}$. Итого суммарное время обработки $n$ запросов равно $(n \log n)^{3/2}$.

\end{document}
