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

\begin{document}

\renewcommand{\tl}{$0.1$ сек.}
\renewcommand{\ml}{$512$ MB}
\problem{Задача B2. OR и AND}
\addauthor{Автор: Петър Петров}{2025}{11}{22}
\renewcommand{\header}{
	НАЦИОНАЛЕН ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА\\
	София, 21 – 23 ноември 2025 г.\\
	Група B – 9, 10 клас
}

Дадена е цяло положително число $K$ (брой битове) и редица от $N$ цели неотрицателни $K$-битови числа $A_0, A_1, \ldots, A_{N-1}$. За всеки интервал $[L,R]$ ($0 \le L \le R < N$) дефинираме $OR(L,R) = A_L \,|\, A_{L+1} \,|\, \ldots \,|\, A_R$, т.е. побитово ИЛИ на всички елементи в интервала, и $AND(L,R) = A_L \,\&\, A_{L+1} \,\&\, \ldots \,\&\, A_R$, т.е. побитово И на всички елементи в интервала.

Напишете програма \textbf{\texttt{oriand}}, която намира броя интервали $[L,R]$ ($0 \le L < R < N$), които могат да се разделят на два интервала $[L,M]$ и $[M+1,R]$ ($L \le M < R$), такива че $OR(L,M) = 2^K-1$ и $AND(M+1,R) = 0$.

\subsection{Детайли по имплементацията}
Трябва да имплементирате функцията \texttt{oriand}:
\begin{lstlisting}
long long oriand(int N, int K, std::vector<long long> A)
\end{lstlisting}
\begin{itemize}
	\item $A$: вектор, съдържащ елементите на редицата, където $A_i=A[i]$;
\end{itemize}

Тази функция ще бъде извикана веднъж за всеки тест и трябва да върне едно цяло неотрицателно число -- броя интервали $[L,R]$, които отговарят на условието.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq N \leq 10^6$;
    \item $1 \leq K \leq 63$;
	\item $0 \leq A_i \leq 2^K-1$.
\end{itemize}

\subsection{Подзадачи}
\begin{table}[ht]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Точки} & \textbf{Необходими подзадачи} & $N$ & \textbf{Други ограничения}\\
		\hline
		$0$ & $0$ & $-$ & $-$ & Примерите. \\ 
		\hline
		$1$ & $9$ & $-$ & $\leq 10^2$ & -- \\ 
		\hline
		$2$ & $11$ & $1$ & $\leq 5 \times 10^2$ & -- \\ 
		\hline
		$3$ & $11$ & $1-2$ & $\leq 10^4$ & -- \\
		\hline
		$4$ & $14$ & $-$ & $\leq 9 \times 10^4$ & $K=1$ \\
		\hline
		$5$ & $13$ & $1-4$ & $\leq 9 \times 10^4$ & -- \\
		\hline
		$6$ & $11$ & $1-5$ & $\leq 2.5 \times 10^5$ & -- \\
		\hline
		$7$ & $31$ & $1-6$ & $\leq 10^6$ & -- \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}

\clearpage

\subsection{Примери}
%\begin{table}[ht]
\begin{tblr}{|l|l|l|}
	\hline
	\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение} \\
	\hline
	\texttt
	{\makecell[lt]{6 1\\1 0 0 0 1 0}} & \texttt{9} & {Търсените интервали са: $[0,1],[0,2],[0,3],[0,4],[0,5],$\\$[1,5],[2,5],[3,5],[4,5]$} \\
	\hline
	\texttt
	{\makecell[lt]{7 3\\7 0 1 2 4 7 0}} & \texttt{11} & {Търсените интервали са: $[0,1],[0,2],[0,3],[0,4],[0,5],$\\$[0,6],
		[1,6],[2,6],[3,6],[4,6],[5,6]$} \\
	\hline
	\texttt
	{\makecell[lt]{7 3\\7 6 5 4 3 2 1}} & \texttt{8} & {Търсените интервали са: $[0,4],[0,5],[0,6],[1,4],[1,5],$\\$[1,6],[2,6],[3,6]$} \\
	\hline
\end{tblr}
%\end{table}

\subsection{Локален грейдър}
Формат на входа:
\begin{itemize}
	\item ред $1$: две цели числа $N$ и $K$;
	\item ред $2$: $N$ цели неотрицателни числа $A_0\ A_1\ \dots\ A_{N-1}$ -- елементите на редицата.
\end{itemize}

Формат на изхода:
\begin{itemize}
	\item ред $1$: едно цяло число -- върнатата стойност при извикването.
\end{itemize}
\FloatBarrier


\end{document}
