\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{0cm}

\begin{document}

\renewcommand{\tl}{$4.5$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача T5. УНИКАЛНИ ЕЛЕМЕНТИ}
\addauthor{Автор: Илиян Йорданов}{2026}{01}{31}
\renewcommand{\header}{
	ЗИМНИ СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА\\
	``Д-р Младен Манев"\\
	Габрово, 31 януари 2026 г.\\
	Група T (отборен формат)
}

\textbf{Д}ени разполага с голям, някои биха казали даже огромен, масив с $N$ елемента със стойности между $1$ и $N$. Тя започва да го изследва като разглежда негови подмасиви и намира броя \textbf{уникални} стойности в тях (една стойност е уникална за даден подмасив, ако се среща точно веднъж в него). От време на време \textbf{Д}ени решава да освежи масива и затова променя някои негови елементи. Тя бързо се уморява да извършва всички тези изследвания, затова напишете програма \textbf{\texttt{unique}}, която да извършва дейностите вместо нея.

\subsection{Детайли по имплементацията}
Трябва да имплементирате функцията \texttt{init}:
\begin{lstlisting}
   void init (std::vector <int> A)
\end{lstlisting}
\begin{itemize}
	\item $A$: началните елементи на масива с големина $N$ със стойности между $1$ и $N$.
\end{itemize}

Тази функция ще бъде извикана веднъж в началото на всеки тест. След това ще бъдат извиквани следните функции за изследване на подмасиви и промяна на стойности:
\begin{lstlisting}
   std::vector <int> queries (std::vector <std::pair <int, int>> S)
\end{lstlisting}
\begin{itemize}
	\item $S$: масив с двойки индекси $0 \le l_i \le r_i \le N-1$, които задават левия и десния край на подмасиви за изследване.
\end{itemize}
\begin{lstlisting}
   void update (int I, int V)
\end{lstlisting}
\begin{itemize}
	\item $I$: индексът на елемента, който ще се промени;
	\item $V$: новата стойност на този елемент, като винаги $1 \le V \le N$.
\end{itemize}

За всяко извикване на първата функция, трябва да се върне масив с броя уникални стойности в съответните подмасиви в реда, в който са зададени.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \le N \le 10^5$
	\item $1 \le Q \le 10^5$ и $0 \le U \le 10^4$, където $Q = E + U$ за $E$ -- общия брой подмасиви за изследване, а $U$ -- брой промени.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{№} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N, Q$ & \textbf{Други ограничения}\\
		\hline
		$1$ & $10$ & $-$ & $\le 10^4$ & -- \\ 
		\hline
		$2$ & $15$ & $-$ & \SetCell[r=5]{}{$\le 10^5$} & $U = 0$ и има едно извикване на \texttt{queries}. \\
		\hline
		$3$ & $13$ & $-$ & & $U = 0$ и $(*)$. \\
		\hline
		$4$ & $17$ & $2-3$ & & $U = 0$. \\
		\hline
		$5$ & $15$ & $3$ & & $(*)$ \\
		\hline
		$6$ & $30$ & $1-5$ & & -- \\
		\hline
	\end{tblr}
	\caption*{\small{Чрез $(*)$ e означено следното ограничение: за всеки изследван подмасив, всяка стойност се среща най-много два пъти в него.}}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

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

\subsection{Локален грейдър}
Формат на входа:
\begin{itemize}
	\item ред $1$: две цели числа $N$ и $Q$ -- брой елементи на масива и общ брой на всички изследвания и промени;
	\item ред $2$: булева стойност $f$ -- флаг, който при стойност $1$ задава, че няма да има промени и всички изследвания ще бъдат подадени с едно извикване на \texttt{queries}, а при стойност $0$ -- всяко изследване ще бъде подадено с различно извикване;
	\item ред $3$: $N$ цели числа -- началните елементи на масива;
	\item ред $4$ до $4+Q-1$: $t$, $x$ и $y$, задаващи при $t=1$ изследване на подмасив между индекси $x$ и $y$, а при $t=2$ промяна на стойността на индекс $x$ на $y$.
\end{itemize}

Формат на изхода:
\begin{itemize}
	\item ред $i$: върнатите стойности при $i$-тото извикване на \texttt{queries}.
\end{itemize}

\end{document}