Estou tentando encontrar uma solução para este desafio:
Dado é n, que é o tamanho de um array preenchido com uns. Há dois tipos de operações possíveis neste array:
- Aumentar (x, y, m): adiciona m a todos os elementos da matriz no intervalo da posição x até y (inclusive). 1 <= x <= y <= n.
- Dê (x, y): retorna o comprimento máximo de uma sequência não decrescente no intervalo fornecido.
Exemplo:
Entrada:
n = 5:Operações:
Aumentar 1 2 3 (x = 1, y = 2, m = 3)
Agora nossa matriz é
[4, 4, 1, 1, 1]Dê 2 4 (x = 2, y = 4)
O comprimento máximo é 2 porque a sequência máxima não decrescente é 1, 1.
Procuro uma solução em que cada operação tenha complexidade de tempo O(log(n)).
Minha abordagem
Notei que podemos armazenar esse array como um array de zeros, onde cada elemento representa como ele é maior que o anterior. Por exemplo, em vez de [1, 4, 2, 5]temos [0, 3, -2, 3]. Agora podemos encontrar facilmente sequências não decrescentes apenas olhando para números negativos. Tentei ir por esse caminho e otimizar a localização de números negativos (por exemplo, usando um conjunto ou árvore), mas para algumas situações a operação "Give" ainda terá uma complexidade O(n), que não é o que eu quero.
Aqui está como meu algoritmo funcionou:
Observe que, se usarmos um array de zeros, podemos alterá-lo (quando houver operação de aumento) em apenas duas etapas: arr[x] += m e arr[y + 1] -= m (presumo que arr seja baseado em 1). No começo, tenho um novo conjunto vazio. Durante a operação de aumento, faço essas duas etapas acima e então:
Se arr[x] após a operação "+= m" não for menor que 0, basta remover x do conjunto.
Se arr[y + 1] após a operação "-= m" não for mais igual ou maior que 0, basta adicionar y + 1 ao conjunto.
Depois de todas as operações de aumento, teremos um conjunto de todos os números negativos. E como escrevi acima, esses são intervalos não decrescentes. Por exemplo, se tivermos n = 6e set = {2, 6}, teremos 3 intervalos não decrescentes: (1, 1), (2, 5), (6, 6). Então, podemos fazer operações Give em O(set.size()), o que não é bom.
Como posso executar cada operação com complexidade de tempo O(logn)?