A ONI é uma empresa multinacional de software responsável por grandes produtos como o Orgzl, o Noxit e o Izuir. Para criar tão excelentes productos, a ONI precisa de manter um registo de todas as tarefas que ainda estão por acabar, assim como a relação entre elas. A tua tarefa é ajudar a ONI a implementar uma ferramenta que os ajuda a organizar as suas tarefas.
A cada tarefa é associado um número de identifição (inteiro positivo), começando com a primeira tarefa de concluir o software (com número de identificação 1). Como muitas das tarefas (incluindo acabar o software!) são muito complexas, a ONI quer ser capaz de criar sub-tarefas para manter os seus engenheiros focados e organizados. Em particular, especificando um número de identificação X e um inteiro n, a ferramenta tem de adicionar n sub-tarefas à tarefa X. Para cada tarefa adicionada, o número de identificação é atribuído de forma sequencial pelo sistema (se x é for maior número de identificação usado até então, as tarefas adicionadas terão números x+1, x+2,...,x+n).
Felizmente, os engenheiros da ONI são naturalmente organizados e quando adiconam sub-tarefas a uma particular tarefa, garantem que não haverá mais adições a essa tarefa.
Ao mesmo tempo, trabalham arduamente (e produtivamente) para que as tarefas não se amontoem, e quando removem uma tarefa (por ter sido concluída), garantem que todas as suas sub-tarefas também estão concluídas e devem ser removidas. Nota que quando uma tarefa é removida o seu número de identificação nunca é reutilizado posteriormente.
Para garantir que o projecto está em bom caminho, o supervisor do projecto quer saber, sempre que há uma modificação das tarefas, quantas tarefas ainda estão por fazer.
Vejamos um exemplo:
A imagem seguinte representa esta situação
Dado um número Q de operações, que podem ser adições ou remoções, calcular o número total de tarefas que ainda estão por concluir no fim de cada operação.
A primeira linha contém um inteiro Q que corresponde ao número de operações a considerar.
Seguem-se Q linhas, representando as operações a efetuar, no seguinte formato:
É garantido que os números de identificação X representam sempre tarefas existentes, e que uma mesma tarefa nunca será alvo de duas operações de adição.
Para cada operação, uma linha contendo o número total de tarefas restantes após a operação.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
1 ≤ Q ≤ 100 000 | Número de operações | |
1 ≤ n ≤ 1 000 000 000 | Números de filhos adicionados numa operação |
Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:
Grupo | Número de Pontos | Restrições adicionais |
---|---|---|
1 | 10 | Q ≤ 15, n ≤ 50 |
2 | 15 | Q ≤ 1 000, n ≤ 1 000 |
3 | 15 | A remoção de tarefas ocorre após todas as adições |
4 | 30 | n ≤ 100 000 |
5 | 30 | - |
5 A 1 5 A 3 3 R 5 A 4 2 R 3
6 9 8 10 6
Este exemplo corresponde ao mencionado no enunciado.
4 A 1 3 R 4 A 2 2 R 6
4 3 5 4