87 lines
2.6 KiB
TeX
87 lines
2.6 KiB
TeX
\documentclass{maratona}
|
|
|
|
\begin{document}
|
|
\begin{ProblemaAutor}{}{K-esimo Um}{1}{1024}{Codeforces EDU}
|
|
|
|
Você deve manter um vetor binário, isto é, um vetor cujos elementos são apenas
|
|
0 ou 1. Inicialmente, o vetor possui $N$ elementos.
|
|
|
|
Serão feitas $M$ operações sobre o vetor. Existem dois tipos de operação:
|
|
|
|
\begin{itemize}
|
|
\item inverter o valor de uma posição, trocando 0 por 1 ou 1 por 0;
|
|
\item encontrar a posição do $k$-ésimo valor 1 no vetor.
|
|
\end{itemize}
|
|
|
|
Os valores 1 são numerados a partir de 0, da esquerda para a direita. Portanto,
|
|
o valor de $k = 0$ representa o primeiro 1 do vetor, $k = 1$ representa o segundo
|
|
1, e assim por diante.
|
|
|
|
Para cada consulta do segundo tipo, imprima o índice do 1 correspondente.
|
|
|
|
\Entrada
|
|
|
|
A primeira linha contém dois inteiros $N$ e $M$
|
|
($1 \leq N, M \leq 10^5$), o tamanho do vetor e o número de operações.
|
|
|
|
A segunda linha contém $N$ inteiros $a_i$, cada um igual a 0 ou 1, representando
|
|
o estado inicial do vetor.
|
|
|
|
As próximas $M$ linhas descrevem as operações. Cada operação tem um dos formatos:
|
|
|
|
\begin{itemize}
|
|
\item \texttt{1 i}: inverta o elemento de índice $i$;
|
|
\item \texttt{2 k}: imprima o índice do $k$-ésimo valor 1 do vetor.
|
|
\end{itemize}
|
|
|
|
Todos os índices são baseados em 0. Para toda operação do segundo tipo, é
|
|
garantido que existem pelo menos $k+1$ valores 1 no vetor no momento da consulta.
|
|
|
|
\Saida
|
|
|
|
Para cada operação do tipo \texttt{2 k}, imprima uma linha contendo o índice do
|
|
$k$-ésimo valor 1 no vetor.
|
|
|
|
\ExemploEntrada
|
|
\begin{Exemplo}
|
|
\texttt{5~8} & \texttt{0}\\
|
|
\texttt{1~0~1~1~0} & \texttt{3}\\
|
|
\texttt{2~0} & \texttt{2}\\
|
|
\texttt{2~2} & \texttt{4}\\
|
|
\texttt{1~0} & \texttt{4}\\
|
|
\texttt{2~0} & \\
|
|
\texttt{1~4} & \\
|
|
\texttt{2~2} & \\
|
|
\texttt{1~2} & \\
|
|
\texttt{2~1} & \\
|
|
\rowcolor{gray!20}\texttt{1~4} & \texttt{0}\\
|
|
\rowcolor{gray!20}\texttt{1} & \texttt{0}\\
|
|
\rowcolor{gray!20}\texttt{2~0} & \\
|
|
\rowcolor{gray!20}\texttt{1~0} & \\
|
|
\rowcolor{gray!20}\texttt{1~0} & \\
|
|
\rowcolor{gray!20}\texttt{2~0} & \\
|
|
\texttt{6~7} & \texttt{5}\\
|
|
\texttt{1~1~1~1~1~1} & \texttt{4}\\
|
|
\texttt{2~5} & \texttt{1}\\
|
|
\texttt{1~5} & \texttt{4}\\
|
|
\texttt{2~4} & \\
|
|
\texttt{1~0} & \\
|
|
\texttt{2~0} & \\
|
|
\texttt{1~3} & \\
|
|
\texttt{2~2} & \\
|
|
\end{Exemplo}
|
|
|
|
|
|
|
|
\Notas
|
|
|
|
No primeiro exemplo, o vetor inicial é \texttt{[1, 0, 1, 1, 0]}. O primeiro 1
|
|
está no índice 0, e o terceiro 1 está no índice 3. Depois das inversões, as
|
|
posições dos valores 1 mudam, e as consultas seguintes refletem esse novo
|
|
estado.
|
|
|
|
Problema adaptado do Codeforces EDU, módulo de árvore de segmentos:
|
|
\textit{B. K-th one}.
|
|
\end{ProblemaAutor}
|
|
\end{document}
|