Solução Informática - Nível Iniciante - Semana 8

Solução Por Pedro Racchetti

Conhecimentos Utilizados:

• Soma de Prefixos

Para esse problema, deve-se ver que um certo elemento $i$ na lista será o somatório de todos os $x$ de operações com intervalos que contém $i$. Outra observação importante é que as perguntas são feitas depois das operações, ou seja, podemos processar todas as operações antes de processar as perguntas.

Com isso, podemos usar a soma de prefixo, da seguinte maneira: Adicionamos o valor $x$ de um intervalo em $l$ e o valor $-x$, em $r + 1$, pois isso garante que em todos os intervalos, x será somado apenas nos elementos do intervalo.

Sabendo disso, podemos processar as operações ao utilizar o método acima, e então efetuar a soma de prefixos, e então, basta imprimir o valor de índice de cada pergunta.

Complexidade: $O(u + n + q)$

Segue o código, comentado, para melhor compreensão: