% !TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{2cm}

\begin{document}
	
\renewcommand{\tl}{$0.3$ сек.}
\renewcommand{\ml}{$256$ MB}
\problem{Задача T81. БОРБА}
\addauthor{Автор: Иван Лупов (заета)}{2026}{08}{28}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	КОНТРОЛНО СЪСТЕЗАНИЕ\\
	Габрово, 28 август 2026 г.\\
	8 клас
}

Нека дефинираме \textit{резултата на борба} върху редицата $b_1, b_2, \dots, b_m$ като величината $b_1 - b_2 + b_3 - b_4 + \dots = \sum_{i=1}^m (-1)^{(i + 1)} \times b_i$. Напишете програма \texttt{\textbf{battle}}, която обработва следните заявки върху въведената редица $a_1, a_2, \dots, a_N$:

\begin{itemize}
\item $1$ $x$ $v$ -- промяна на стойността на $a_x$ на $v$;
\item $2$ $l$ $r$ $v$ -- промяна на стойностите на $a_l, a_{l + 1}, \dots, a_r$ на $v$;
\item $3$ $l$ $r$ -- въпрос колко може да е най-големият резултат на борба върху подредица $a_x, a_{x + 1}, \dots, a_y$ за $l \le x \le y \le r$.
\end{itemize}

\subsection{Вход}

От първия ред на стандартния вход се въвеждат $N$ и $Q$ -- дължината на редицата и броят заявки, които ще се обработват. От втория ред се въвеждат $N$ числа -- $a_1, a_2, \dots, a_N$. От всеки от следващите $Q$ реда се въвежда по едно описание на заявка.

\subsection{Изход}

На стандартния изход изведете по едно число, представляващо съответния отговор, за всяка заявка от тип $3$.

\subsection{Ограничения}
\begin{itemize}
	\item $1 \le N, Q \le 10^5$
	\item $0 \le a_i, v \le 10^9$
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N, Q$ & \textbf{Други ограничения}\\
        \hline
        	$0$ & $ 0$ & $ - $ & $-$ & Примерният тест.\\ 
        \hline
        	$1$ & $20$ & $ 0 $ & $\le 1000$ & $N \le 100$. Няма заявки от тип $2$.\\ 
       	\hline
			$2$ & $20$ & $0-1$ & $\le 5000$ & Няма заявки от тип $2$.\\ 
       	\hline
			$3$ & $30$ & $0-2$ & $\le 10^5$ & Няма заявки от тип $2$.\\ 
       	\hline
			$4$ & $30$ & $0-3$ & $\le 10^5$ & -- \\ 
        \hline
    \end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|X[j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt{\makecell[lt]{
		    10 6\\
		    5 9 1 2 3 4 6 4 2 8\\
		    3 3 7\\
		    3 4 10\\
		    3 6 9\\
		    1 5 8\\
		    3 1 10\\
		    3 4 6
		}} & 
		\texttt{\makecell[lt]{6\\10\\6\\10\\8}} &
		Отговорът на втория въпрос се намира като борбата на редица $4, 2, 8$: $4 - 2 + 8 = 10$. \\
		\hline
	\end{tblr}
\end{table}

\end{document}
