\Section{RMQ $\pm$1, LCA}{?? ??}{Михаил Азанов}

\Subsection{RMQ $\pm$1}

\t{[$\mathcal{O}(n), \mathcal{O}(1)$]}

\begin{enumerate}
    \item Разделяем массив на куски по $\frac{1}{2} \log n$. По минимумам на каждом куске строим $SparseTable$.
    \item Если при запросе $L, R$ попадают в разные блоки, берем минимум из блоков, попавших целиком (тут поможет $SparseTable$), осталось только рассмотреть случай, когда $L, R$ - в одном и том же блоке.
    \item Заметим, что вариантов того, как может быть устроен этот маленький блок не так уж и много, а именно не больше, чем $2^(\frac{1}{2} \log n) = \sqrt{n}$. Здесь мы пользуемся тем, что соседние элементы отличаются на $\pm$1, поэтому можно массив заменить на массив из плюс-минус-единиц. Конечно, потому что нам важно только расположение минимума в данном случае.
    \item Мало вариантов внутреннего устройства подотрезка, поэтому мы делаем предподсчет, тем самым добиваясь ответа на вопрос за $\mathcal{O}(1)$.
    \item На лекции предлагалось в реализации хранить подотрезки по маске, заминив \t{+1} на \t{0}, \t{-1} на \t{1},
       и делать запрос к предподсчету по элементу $f[(x_i \t{>>} L) \t{\&} (2^{R-L} - 1)]$. 
       Последняя часть, чтобы откинуть лишние биты. Утверждается, что это можно сделать и это даже будет работать для префиксов, 
       в чем не трудно убедиться самостоятельно.
\end{enumerate}


\Subsection{LCA}

\t{Способы решать задачу:}
\begin{enumerate}
    \item Сводим к $RMQ, SparseTable$. Online [$\mathcal{O}(n\log n), \mathcal{O}(1)$], offline [$\mathcal{O}(n),\mathcal{O}(\log n)$]
    \item Двоичные подъемы. [$\mathcal{O}(n\log n)$]
    
    $go[k,v] = go[k-1,go[k-1,v]]$
    
    $go[0,v] = parent[v]$
    
    $parent[root] = root$
    
    $dep[v]$ - глубины вершин.
    
    Собственно, функция LCA (работает за $\mathcal{O}(\log n)$):
    
    \begin{code}
    
    LCA(a,b) {
        if(dep[a] > dep[b])
            Jump(a, dep[a] - dep[b])
        else
            Jump(b, dep[b] - dep[a])
    
        FOR k = log2(n) .. 0
            if (go[a,k] != go[b,k])
                a = go[a,k]
                b = go[b,k]
    
        return a == b ? a : parent[a]
    }
    \end{code}
    \item Времена входа-выхода.
    
    \begin{code}
        
        // O(n)
        dfs(v) {
            in[v] = T++
            for(int x : g[v])
                dfs(x)
            out[v] = T++
        }
        
        // O(1)
        bool is_ancestor(int a, int b) {
            return in[a] <= in[b] && out[a] >= in[b];
        }
        
        int LCA2(int a, int b) {
            for k = log2(n) .. 0
                if (!is_ancestor(go[a,k], b])
                    a = go[a,k];
                return is_ancestor(a,b) ? a : parent[a];
        }
        
    \end{code}
    
\end{enumerate}
