% !TeX program=lualatex

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

\begin{document}
	
	\renewcommand{\tl}{$0.3$ сек.}
	\renewcommand{\ml}{$256$ MB}
	\problem{Задача GT13. СКЛАД}
	\addauthor{Автор: Петър Петров}{2030}{12}{20}
	\renewcommand{\header}{
		ТРЕНИРОВЪЧНО СЪСТЕЗАНИЕ\\
		НА РАЗШИРЕНИЯ НАЦИОНАЛЕН ОТБОР\\
		София, 2 май 2026 г.\\
		Група G
	}
	
	В голям склад има $n$ кашона, подредени в редица и номерирани от $1$ до $n$.  
	Всеки кашон има етикет -- цяло число $a_i$, което обозначава вида на съдържанието му.
	
	Инспекторът на склада извършва проверки. При всяка проверка той избира интервал от кашони $[l, r]$.
	
	Един вид кашони с етикет $x$ се нарича \textit{правилно подреден} в интервала, ако:
	
	\[
	\text{в интервала има точно } x \text{ кашона с етикет } x.
	\]
	
	Например, ако $x = 3$, то в разглеждания интервал трябва да има точно $3$ кашона с етикет $3$.
	
	\textbf{Забележка:} броим различните стойности $x$, които удовлетворяват условието.
	
	Напишете програма \texttt{\textbf{warehouse.cpp}}, която за всяка проверка намира броя на правилно подредените видове кашони.
	
	\subsection{Вход}
	От първия ред на стандартния вход се въвеждат три цели числа $n$, $q$ и $c$ -- съответно броят на кашоните, броят на проверките и параметърът за кодиране на заявките.
	
	От втория ред се въвеждат $n$ цели числа $a_1, a_2, \dots, a_n$ -- етикетите на кашоните.
	
	Всеки от следващите $q$ реда съдържа по две цели числа $l$ и $r$.
	
	Ако $c = 0$, числата $l$ и $r$ са директно границите на проверката.
	
	Ако $c = 1$, заявките са кодирани. Нека $ans_i$ е отговорът на $i$-тата заявка, като $ans_0 = 0$. Тогава за $i$-тата заявка истинските граници се получават така:
	\[
	l = l \oplus ans_{i-1}, \qquad r = r \oplus ans_{i-1},
	\]
	където $\oplus$ означава побитово изключващо или (xor).
	
	Гарантирано е, че след евентуалното декодиране е изпълнено $1 \leq l \leq r \leq n$.
	
	\subsection{Изход}
	За всяка заявка изведете на отделен ред едно цяло число -- броя на различните етикети $x$, за които има точно $x$ кашона с етикет $x$ в интервала $[l, r]$.
	
	\subsection{Ограничения}
	\begin{itemize}
		\item $1 \leq n, q \leq 100~000$
		\item $1 \leq a_i \leq 10^6$
		\item $c \in \{0, 1\}$
	\end{itemize}
	\FloatBarrier
	\pagebreak
	
\subsection{Подзадачи}
\begin{table}[H]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $n, q$ & $c$ & \textbf{Други ограничения}\\
		\hline
		$1$ & $5$ & $-$ & $\le 1000$ & $0$ & -- \\
		\hline
		$2$ & $20$ & $1$ & $\le 20~000$ & $0$ & -- \\
		\hline
		$3$ & $10$ & $-$ & $\le 100~000$ & $0$ & Всички заявки са с $l = 1$. \\
		\hline
		$4$ & $15$ & $-$ & $\le 100~000$ & $0$ & Всички $a_i \le 100$. \\
		\hline
		$5$ & $20$ & $1-4$ & $\le 100~000$ & $0$ & -- \\
		\hline
		$6$ & $30$ & $1-5$ & $\le 100~000$ & $0,1$ & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
	\FloatBarrier
	
	\subsection{Примери}
	\begin{table}[H]
		\begin{tblr}{width={\linewidth},colspec={|X[l]|X[l]||X[l]|X[l]|}}
			\hline
			\textbf{Вход 1} & \textbf{Изход 1} & \textbf{Вход 2} & \textbf{Изход 2} \\
			\hline
			\texttt{\makecell[lt]{7 3 0\\1 2 2 3 3 3 2\\1 7\\1 3\\4 6}} & \texttt{\makecell[lt]{2\\2\\1}} &
			\texttt{\makecell[lt]{5 2 0\\1 1 1 1 1\\1 5\\2 4}} & \texttt{\makecell[lt]{0\\0}}\\
			\hline
		\end{tblr}
	\end{table}
	
	\subsection{Обяснение на пример 1}
	За заявката $[1,7]$:
	\begin{itemize}
		\item етикет $1$ се среща $1$ път $\Rightarrow$ валиден
		\item етикет $2$ се среща $3$ пъти $\Rightarrow$ не е валиден
		\item етикет $3$ се среща $3$ пъти $\Rightarrow$ валиден
	\end{itemize}
	Следователно отговорът е $2$.
	
\end{document}