Pergunta de consulta de intervalo CSES: consultas de salário

Aug 18 2020

Estou tentando resolver este problema:https://cses.fi/problemset/task/1144/

Dada uma matriz de até 200000elementos, minha tarefa é processar até 200000consultas, que me pedem para atualizar um único valor dentro da matriz ou me pedem para encontrar o número de elementos entre a e b que estão em um determinado intervalo (para Por exemplo, uma consulta perguntaria quantos elementos de índices 1a 5estão no intervalo [2, 3]).

Minha ideia atual é primeiro usar a compactação de índice nos valores da matriz fornecida (já que os valores podem ser até 10^9, portanto, manter uma matriz de ocorrência simples excederia os limites de armazenamento) e, em seguida, manter outra matriz que contenha o número de ocorrências de cada compactado número. Então, o processamento e a atualização das consultas podem ser feitos usando uma árvore de segmento de soma.

No entanto, tive um problema ao tentar implementar essa abordagem. Percebi que atualizar um único valor de array me forçaria a alterar o array compactado.

Por exemplo, dado um array [1, 5, 3, 3, 2], eu definiria uma função de compressão Ctal que

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

Então, a matriz de ocorrências seria [1, 1, 2, 1], e o processamento de consultas de soma seria eficiente. No entanto, se eu fosse instruído a atualizar um valor, digamos, alterar o terceiro elemento para 4, isso desequilibraria tudo. A função de compressão teria que mudar para

C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

o que me forçaria a reconstruir minha matriz de ocorrências, resultando em O(N)tempo de atualização.

Como Npode ser até 200000, minha abordagem atual não funcionará com eficiência suficiente para resolver o problema, embora eu ache que tenho a ideia certa com compactação de índice. Alguém por favor pode me apontar na direção certa com o meu método?

Respostas

6 Telescope Aug 18 2020 at 06:09

Você tem a ideia certa ao usar a compactação de índice - ótima ideia! Como Ncabe somente a 200000, manter um array de ocorrências exigirá no máximo 200000elementos para os valores iniciais do array dado, ao invés de 10^9índices de array.

De acordo com você, o problema que você enfrenta é quando encontra novos valores durante o processamento das consultas. Você tem razão; isso desequilibraria a matriz de ocorrências e faria com que as atualizações fossem executadas a O(N)tempo. A solução para esse problema é apenas uma pequena modificação em seu método atual.

Para resolver o problema de encontrar novos valores, podemos apenas garantir que nunca encontraremos novos valores. Podemos fazer isso lendo todas as consultas antes de construir a árvore de segmento de soma. Isso resultará em um máximo de N + 2*Qvalores exclusivos ou, 600000no pior caso, o suficiente para construir uma matriz de ocorrência com o limite de armazenamento de 512 MB do problema. Depois disso, uma árvore de segmento de soma será capaz de responder a essas consultas com eficiência.

Portanto, no final, uma estratégia para resolver esse problema seria inserir todos os números exclusivos, construir uma função de compactação de índice e usar uma árvore de segmento de soma para processar com eficiência as consultas de soma.

No futuro, lembre-se de que, nesses tipos de perguntas de resposta a consultas, pode ser útil ler TODAS as entradas antes da pré-computação . Boa sorte com seu programa.

3 JacobSteinebronn Aug 18 2020 at 01:41

Primeiro, considere o ingênuo: para cada atualização, atualize o array. Para cada consulta, examine toda a matriz e colete sua resposta. A complexidade desta solução tem O(n)atualizações, O(n)consultas. Nada de bom.

Podemos chegar a uma solução diferente com complexidade de tempo indiscutivelmente pior, mas isso nos dá uma dica de qual é o nosso resultado final. Mantenha a matriz de origem em todos os momentos, mas também mantenha um mapa de hash de valor->frequência. Então, quando você atualizar, diminua a frequência no valor antigo e incremente-a no novo valor. Agora, para consultas, percorra todos os valores desse intervalo de consulta e some-os para sua resposta. Isso resulta em O(1)atualizações e O(r-l)consultas, portanto, temos atualizações excelentes, mas consultas terríveis. No entanto, esse resultado pode ser melhorado se pudermos apenas acelerar essas consultas! Entre na Árvore de Segmentos .

Tradicionalmente, você construiria uma árvore de segmentos até suas folhas durante a criação. No entanto, gostaríamos nominalmente de uma árvore de segmentos que varia de 0-10^9, então não há absolutamente nenhuma maneira de gerar tanta memória (e teríamos tempo limite ao fazê-lo). No entanto, e se criarmos uma árvore de segmentos, mas para cada nó, seus filhos estão implícitos se nunca tiverem sido usados. Ou seja, não crie nós filhos se não houver elementos neles . Essa estrutura é chamada, apropriadamente, de Árvore de Segmentos Implícitos. A ideia aqui é implementar sua árvore de segmentos normalmente, exceto pular a parte no construtor onde você inicializa seus filhos esquerdo e direito. Agora, quando você precisar aprofundar seus filhos devido a uma consulta de intervalo parcial, verifique se eles existem e, se não, crie-os. Caso contrário, como você nunca precisou criá-los, suponha que a soma dos valores nesses nós seja 0!

A solução final é a seguinte: Crie uma árvore de segmentos do valor máximo que pode ser consultado (se você não precisar responder interativamente, considere salvar e escanear suas consultas para encontrar o valor r máximo, mas não é necessário). Observe para tornar isso uma árvore de segmento implícita . Mantenha a matriz de origem após cada atualização e também faça atualizações pontuais em sua árvore, que serão O(log(max value)). As consultas são consultas de intervalo de árvore de segmento regular, portanto, serão O(log(max value)). E aí está!

1 rootkonda Aug 18 2020 at 03:21

Você pode usar a estrutura de dados baseada em políticas, que possui alguns métodos úteis, como order_of_key() - que retorna um número de itens menor que o número fornecido. Podemos chamar isso duas vezes como getcnt(b+1) - getcnt(a) - que fornece a contagem de itens entre o intervalo especificado. Para mais informações sobre isso - você pode consultar -https://codeforces.com/blog/entry/11080e tambémhttps://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html

Depois de muita pesquisa, descobri que este STL é muito útil ao usar estruturas baseadas em árvore.

Eu testei o código abaixo e ele passou em todos os casos de teste.

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
 
using namespace std;
using namespace __gnu_pbds;
 
template<class T> using cust_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
cust_set<array<int,2>> freq;
 
int getcnt(int x)
{
    return freq.order_of_key({x,0});
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    vector<int> emp(n);
    
    int sal;
    for(int i=0;i<n;i++)
    {
        cin >> emp[i];
        freq.insert({emp[i],i});
    }
    char c;
    int x,a,b;
    while(q--)
    {
        cin>> c;
        int ans=0;
        if(c=='?')
        {
            cin>>a>>b;
            cout << getcnt(b+1) - getcnt(a)<<"\n";
        }
        else
        {
            cin>>a>>b;
            --a;
            freq.erase({emp[a],a});
            emp[a] = b;
            freq.insert({emp[a],a});
        }
    }
    return 0;
}