Consultas XOR em Intervalos
É fornecido um array de
n elementos e q consultas. Existem dois tipos de consultas:- Obter o XOR (OR exclusivo) do intervalo especificado
- Atualizar o array numa dada posição
A sua tarefa é processar estas consultas de forma eficiente.
Entrada
A primeira linha da entrada contém dois números inteiros
n e q (1 ≤ n, q ≤ 100 000), que representam, respetivamente, o número de elementos no array e o número de consultas.A segunda linha contém
n números inteiros separados por espaços (), que são os valores iniciais do array.As seguintes
q linhas representam as consultas, cada uma em seu próprio formato:- Para consultas XOR em intervalos: a linha começa com o número
1, seguido de dois inteiros e (), que indicam o intervalo de índices[ $$l_i, r_i$$ ]para o qual se deve calcular o valor de XOR.
- Para consultas de atualização do array: a linha começa com o número
2, seguido de dois inteiros e (), que indicam a posição do elemento a atualizar e o novo valor correspondente.
Saída
Para cada consulta XOR em intervalo, imprima o resultado do XOR dos elementos dentro do intervalo especificado, cada um numa nova linha.
Exemplos
Entrada | Saída |
6 4
1 4 2 7 5 3
1 1 3
2 2 9
1 2 5
1 3 6 | 7
9
3 |
Constraints
Time limit: 0.6 seconds
Memory limit: 512 MB
Output limit: 1 MB