\documentclass[12pt]{article}
\input{structure.tex}

\begin{document}

\renewcommand{\tl}{$5$ сек.}
\renewcommand{\ml}{$512$ MB}
\problem{Анализ. МУХЪЛ}
\renewcommand{\header}{
	ЛАГЕР ШКОЛА ЗА\\
	ПОДГОТОВКА НА РАЗШИРЕНИТЕ ОТБОРИ\\
	София, 27 юни 2026 г.\\
	Анализ на задачите
}
~\\

\section*{Подзадача 1 ($T_i = 1$, 4 точки)}
Когато всички пръскания се изпълняват в един и същ ден, заразата няма време да се върне между тях, така че пръсканияте се държат като обикновени отсечки с цени и търсим \emph{най-евтиното покритие} на $[1, N]$ с тях.

Сортираме пръсканияте по десен край $R$ и дефинираме
\[
dp[i] = \min\{\, dp[j] : j \text{ е разгледан преди } i \text{ и } L_i - 1 \leq R_j \,\} + C_i,
\]
т.е.\ най-малката цена да покрием $[1, R_i]$, завършвайки с пръскане $i$ (отделно $dp[i] = C_i$, ако $L_i = 1$). Множеството допустими предшественици $j$ образува \emph{наставка} по стойност на $R_j$, затова минимумът се намира с дърво за интервали (range-min, point-update). Сложност $O(M \log M)$.

\section*{Подзадача 2 ($M \leq 16$, 5 точки)}
Перебираме всичките $2^M$ подмножества от пръскания и за всяко проверяваме дали удовлетворява условието. Тъй като $M$ е малко, проверката може да е „мързелива“ -- например симулация или директна проверка за свързаност между пръскане, съдържащ участък $1$, и пръскане, съдържащ участък $N$. Достатъчно е $O(2^M \cdot M^2)$.

\section*{Подзадача 3 ($M \leq 5\,000$, 30 точки)}
Ключовото наблюдение: при едно валидно решение избраните пръскания образуват \emph{граница} между заразената с мухъл и почистената област, която се „стеснява“ с времето, докато съседни пръскания се захващат един за друг. С други думи, достатъчно е да можем да тръгнем от пръскане, който покрива участък $1$, и следвайки захванати помежду си пръскания да стигнем до пръскане, който покрива участък $N$. Това е \textbf{задача за най-къс път}.

Нека пръскане $a$ може да предаде границата на пръскане $b$. Между моментите $T_a$ и $T_b$ заразата изяжда по $|T_a - T_b|$ клетки от всяка страна, така че излекуваните области се застъпват точно когато
\[
L_b \leq R_a - |T_a - T_b| + 1 \quad\Longleftrightarrow\quad R_a - L_b \geq |T_a - T_b| - 1 .
\]
Тогава строим ориентиран ръб $a \to b$ с цена $C_b$. Изворите са пръсканияте с $L = 1$ (с начална цена $C$), а целта е пръскане с $R \geq N$. Дейкстра по този плътен граф дава отговора за $O(M^2)$.

\section*{Подзадача 4 (без допълнителни ограничения, 61 точки)}
Сега не можем да построим всички $O(M^2)$ ребра. Използваме две свойства на задачата.

\textbf{Свойство 1 (завъртане на $45^\circ$).} Полагаме
\[
X_i = L_i - T_i, \qquad Y_i = L_i + T_i .
\]
Тогава условието $L_b \leq R_a - |T_a - T_b| + 1$ се разпада на \emph{две} независими неравенства:
\[
X_b \leq R_a - T_a + 1 \qquad\text{и}\qquad Y_b \leq R_a + T_a + 1 .
\]
Така пръсканияте, достижими от $a$, са точно тези, чийто ляв край (в координати $X, Y$) попада в правоъгълна област -- наставка по $X$ и наставка по $Y$.

\textbf{Свойство 2 (еднакви цени на входящите ребра).} Всички ребра, влизащи в пръскане $a$, имат една и съща цена $C_a$, независимо от началото си. При Дейкстра това означава, че щом разстоянието до $a$ бъде обновено за първи път, то вече е окончателно -- значи всеки пръскане се „релаксира“ най-много веднъж.

\textbf{Структура от данни.} Сортираме пръсканияте по $X$ и построяваме дърво за интервали, чиито листа са отделни пръскания; всеки вътрешен възел пази пръсканияте от своя $X$-обхват, \emph{сортирани по $Y$} (изграждане чрез сливане, $O(M \log M)$). Изпълняваме Дейкстра: когато извадим пръскане $a$, отиваме до възлите, покриващи $X \leq R_a - T_a + 1$, и във всеки от тях вземаме пръсканияте по нарастващо $Y$, докато $Y \leq R_a + T_a + 1$, като \emph{ги изтриваме} от дървото след обработка. Понеже всеки пръскане се вижда и трие най-много веднъж (Свойство 2), общата работа е $O(M \log M)$ за достъпите до възлите плюс $O(M \log M)$ за изваждането на пръсканияте. Това дава пълните точки.

\section*{Алтернативно пълно решение: едно дърво по $Y$}
Свойство 1 и Свойство 2 позволяват и по-просто пълно решение -- с едно-единствено дърво за интервали, без изграждане чрез сливане.

Компресираме координатата $Y$ (нужно, тъй като $N \leq 10^9$) и индексираме дърво за интервали по нея. Във всяко листо -- фиксирана стойност на $Y$ -- държим още непосетените пръскания с тази координата в \emph{сортиран по $X$} буфер (например \texttt{std::set}); листото пази най-малкото $X$ в буфера, а всеки вътрешен възел -- минимума на $X$ върху своя $Y$-обхват заедно с индекса, който го реализира.

При Дейкстра, щом извадим пръскане $a$, многократно питаме за минимума на $X$ върху \emph{префикса} $Y \leq R_a + T_a + 1$. Докато този минимум е $\leq R_a - T_a + 1$, съответното пръскане $b$ лежи в правоъгълника
\[
X_b \leq R_a - T_a + 1, \qquad Y_b \leq R_a + T_a + 1,
\]
тоест е достижимо: премахваме го от буфера му (и обновяваме листото), релаксираме $dist[b] = dist[a] + C_b$ и продължаваме. Когато минимумът надхвърли $R_a - T_a + 1$, в правоъгълника няма повече непосетени пръскания и спираме.

Понеже всяко пръскане се намира и изтрива най-много веднъж (Свойство 2), правим $O(M)$ успешни заявки плюс по една неуспешна на всяко изваждане от опашката, всяка за $O(\log M)$. Заедно с компресията на координатите сложността отново е $O(M \log M)$ -- също пълни точки, но с осезаемо по-кратка имплементация.

\end{document}
