Informática Avançado – Semana 74

Teste da Árvore de Segmentos

Lowrenzo está fazendo uma prova e se depara com o seguinte problema:

Você tem um vetor de $$N$$ elementos $$(1 \leq N \leq 10^5)$$, indexados de $$1$$ até $$N$$.

Existem $$M$$ $$(1 \leq M \leq 500 000)$$ operações que você precisa fazer.

Cada operações pode ser de uma das seguintes maneiras:

• $$C$$ $$x$$ $$v$$ – Muda o $$x$$-ésimo elemento do array para $$v$$.
• $$M$$ $$l$$ $$r$$ – Imprima o minimo de todos os elementos no intervalo $$l$$ até $$r$$, inclusive.
• $$G$$ $$l$$ $$r$$ – Imprima o MDC(Máximo Divisor Comum) de todos os elementos no intervalo $$l$$ até $$r$$, inclusive.
• $$Q$$ $$l$$ $$r$$ – Imprima a quantidade de números iguais ao resultado da operação $$G$$ $$l$$ $$r$$ entre todos os elementos no intervalo $$l$$ até $$r$$, inclusive.

Todos os elementos no vetor estão entre $$1$$ e $$10^9$$. Ajude Lowrenzo a resolver esse problema.

Entrada

A primeira linha da entrada contém dois inteiros $$N$$ e $$M$$. Na segunda linha da entrada temos $$N$$ inteiros, representando o array original. Cada uma das próximas $$M$$ linhas contém uma das operações que foram explicadas anteriormente.

Saída

Imprima a resposta para todas as operações do tipo $$M$$, $$G$$ e $$Q$$.

Exemplos

Enviar solução: DMOJ