Início / coding / Perguntas / 79310078
Accepted
Donald
Asked: 2024-12-27 01:26:46 +0800 CST

Estrutura de dados para encontrar facilmente o comprimento máximo de uma sequência não decrescente em um determinado intervalo

  • 772

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:

  1. Aumentar 1 2 3 (x = 1, y = 2, m = 3)

    Agora nossa matriz é[4, 4, 1, 1, 1]

  2. 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:

  1. Se arr[x] após a operação "+= m" não for menor que 0, basta remover x do conjunto.

  2. 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)?

algorithm

1 respostas

  1. Best Answer

    Isso pode ser resolvido usando uma árvore de segmento com propagação preguiçosa (alternativamente, os aumentos de intervalo podem ser manipulados separadamente em uma árvore indexada binária). Em cada nó, armazene a soma dos aumentos em ambas as extremidades esquerda e direita do intervalo que o nó representa, bem como o comprimento de três subarrays não decrescentes mais longos: aquele que começa na extremidade esquerda, aquele que termina na extremidade direita e o mais longo geral em qualquer lugar dentro do intervalo do nó. Para um nó folha, todos os três comprimentos são um e começamos com cada nó tendo incremento 0.

    Ao mesclar dois nós, considere se o maior subarray não decrescente terminando no ponto final direito do nó esquerdo pode ser combinado com o maior subarray não decrescente começando no ponto final esquerdo do nó direito verificando se o elemento no ponto final direito do primeiro não é maior do que o elemento no ponto final esquerdo do último, após aplicar aumentos (lembre-se de que a soma das operações de aumento nos pontos finais já está armazenada em cada nó). O maior subarray não decrescente começando no ponto final esquerdo no resultado mesclado terá o mesmo valor que o do nó esquerdo, a menos que o maior subarray não decrescente no nó esquerdo cubra o nó inteiro, caso em que seria o resultado combinado dos nós esquerdo e direito (se fosse possível). O caso do maior subarray não decrescente terminando no ponto final direito é simétrico.

    Para uma operação de aumento que cobre um nó inteiro, todos os subarrays não decrescentes permanecem não decrescentes, pois todos os elementos são incrementados pela mesma quantidade. Só é necessário manter o controle deles como atualizações preguiçosas (empurre as atualizações para baixo assim que um nó for encontrado ao percorrer a árvore de segmentos).

    Tanto consultas quanto atualizações podem ser feitas em O(log(n)).

    Implementação em C++:

    #include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
struct Node {
    int left, right, leftIncr, rightIncr, prefixMax, suffixMax, overallMax, lazy;
};
std::vector<Node> tree;
void pushdown(int n) {
    tree[n].leftIncr += tree[n].lazy;
    tree[n].rightIncr += tree[n].lazy;
    if (tree[n].left != tree[n].right) {
        tree[n * 2].lazy += tree[n].lazy;
        tree[n * 2 + 1].lazy += tree[n].lazy;
    }
    tree[n].lazy = 0;
}
Node merge(Node l, Node r) {
    bool canCombine = l.rightIncr <= r.leftIncr;
    return { 
        l.left, r.right, l.leftIncr, r.rightIncr, 
        l.prefixMax + (l.prefixMax == l.right - l.left + 1 && canCombine) * r.prefixMax, 
        r.suffixMax + (r.suffixMax == r.right - r.left + 1 && canCombine) * l.suffixMax, 
        std::max({l.overallMax, r.overallMax, canCombine * (l.suffixMax + r.prefixMax)})
    };
}
Node build(int n, int l, int r) {
    if (l != r) {
        int mid = std::midpoint(l, r);
        tree[n] = merge(build(n * 2, l, mid), build(n * 2 + 1, mid + 1, r));
    } else {
        tree[n].left = tree[n].right = l;
        tree[n].prefixMax = tree[n].suffixMax = tree[n].overallMax = 1;
    }
    return tree[n];
}
void update(int n, int updateLeft, int updateRight, int incr) {
    pushdown(n);
    if (updateLeft <= updateRight)
        if (tree[n].left == updateLeft && tree[n].right == updateRight) {
            tree[n].lazy = incr;
            pushdown(n);
        } else {
            update(n * 2, updateLeft, std::min(updateRight, tree[n * 2].right), incr);
            update(n * 2 + 1, std::max(tree[n * 2 + 1].left, updateLeft), updateRight, incr);
            tree[n] = merge(tree[n * 2], tree[n * 2 + 1]);
        }
}
Node query(int n, int queryLeft, int queryRight) {
    pushdown(n);
    if (tree[n].left == queryLeft && tree[n].right == queryRight) return tree[n];
    if (queryRight <= tree[n * 2].right) return query(n * 2, queryLeft, queryRight);
    if (queryLeft > tree[n * 2].right) return query(n * 2 + 1, queryLeft, queryRight);
    return merge(query(n * 2, queryLeft, tree[n * 2].right), query(n * 2 + 1, tree[n * 2 + 1].left, queryRight));
}
int main() {
    int n;
    std::cin >> n;
    tree.resize(4 * n);
    build(1, 1, n);
    for (int type, l, r, incr; std::cin >> type >> l >> r;) {
        // type = 1 is query; type = 0 is update
        if (type) std::cout << query(1, l, r).overallMax << '\n';
        else {
            std::cin >> incr;
            update(1, l, r, incr);
        }
    }
}
    • 2

relate perguntas