Domanda sull'intervallo CSES: domande sullo stipendio

Aug 18 2020

sto cercando di risolvere questo problema:https://cses.fi/problemset/task/1144/

Dato un array di fino a 200000elementi, il mio compito è elaborare fino a 200000query, che mi chiedono di aggiornare un singolo valore all'interno dell'array o mi chiedono di trovare il numero di elementi tra a e b che si trovano in un dato intervallo (per esempio, una query chiederebbe quanti elementi dagli indici 1to 5sono nell'intervallo [2, 3]).

La mia idea attuale è quella di utilizzare prima la compressione dell'indice sui valori nell'array dato (poiché i valori possono essere fino a 10^9, quindi mantenere un semplice array di occorrenze supererebbe i limiti di archiviazione), quindi mantenere un altro array che contenga il numero di occorrenze di ciascun compresso numero. Quindi, l'elaborazione e l'aggiornamento delle query potrebbero essere eseguite utilizzando un albero di segmenti di somma.

Tuttavia, ho riscontrato un problema durante il tentativo di implementare questo approccio. Mi sono reso conto che l'aggiornamento di un singolo valore di array mi costringerebbe a modificare l'array compresso.

Ad esempio, dato un array [1, 5, 3, 3, 2], definirei una funzione di compressione Ctale che

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

Quindi, l'array di occorrenza sarebbe [1, 1, 2, 1]e l'elaborazione delle query di somma sarebbe efficiente. Tuttavia, se mi è stato chiesto di aggiornare un valore, ad esempio, di modificare il terzo elemento in 4, ciò sbilancia tutto. La funzione di compressione dovrebbe cambiare in

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

che mi costringerebbe a ricostruire il mio array di occorrenze, con conseguente O(N)tempo di aggiornamento.

Poiché Npuò essere fino a 200000, il mio approccio attuale non funzionerà in modo sufficientemente efficiente per risolvere il problema, anche se penso di avere l'idea giusta con la compressione dell'indice. Qualcuno può indicarmi la giusta direzione con il mio metodo?

Risposte

6 Telescope Aug 18 2020 at 06:09

Hai l'idea giusta nell'usare la compressione dell'indice - ottima idea! Come Nè solo fino a 200000, mantenere un array di occorrenze richiederà al massimo 200000elementi per i valori iniziali dell'array dato, invece degli 10^9indici dell'array.

Secondo te stesso, il problema che devi affrontare è quando incontri nuovi valori durante l'elaborazione delle query. Hai ragione; questo getterebbe fuori equilibrio l'array di occorrenze e causerebbe l'esecuzione tempestiva degli aggiornamenti O(N). La soluzione a questo problema è solo una piccola modifica al tuo metodo attuale.

Per risolvere il problema dell'incontro con nuovi valori, possiamo solo assicurarci di non incontrare mai nuovi valori. Possiamo farlo leggendo tutte le query prima di costruire l'albero dei segmenti di somma. Ciò si tradurrà in un massimo di N + 2*Qvalori univoci o, 600000nel peggiore dei casi, che è sufficiente per costruire un array di occorrenze con il limite di archiviazione di 512 MB del problema. Successivamente, un albero di segmenti di somma sarà in grado di rispondere a queste domande in modo efficiente.

Quindi, alla fine, una strategia per risolvere questo problema sarebbe inserire ogni numero univoco, quindi costruire una funzione di compressione dell'indice, quindi utilizzare un albero di segmenti di somma per elaborare in modo efficiente le query di somma.

In futuro, ricorda che in questo tipo di domande di risposta alle query, potrebbe essere utile leggere TUTTO l'input prima del precomputation . Buona fortuna con il tuo programma.

3 JacobSteinebronn Aug 18 2020 at 01:41

Innanzitutto, considera l'ingenuo: per ogni aggiornamento, aggiorna l'array. Per ogni query, scansiona l'intero array e raccogli la tua risposta. La complessità di questa soluzione ha O(n)aggiornamenti, O(n)query. Non buono.

Possiamo trovare una soluzione diversa con una complessità temporale probabilmente peggiore, ma ci dà un suggerimento su quale sia il nostro risultato finale. Mantieni sempre l'array di origine, ma mantieni anche una mappa hash di valore-> frequenza. Quindi, quando aggiorni, decrementa la frequenza al vecchio valore e incrementala al nuovo valore. Ora, per le query, esegui il ciclo di tutti i valori di quell'intervallo di query e sommali per la tua risposta. Ciò si traduce in O(1)aggiornamenti e O(r-l)query, quindi abbiamo aggiornamenti eccellenti ma query terribili. Tuttavia, questo risultato può essere migliorato se solo possiamo velocizzare quelle query! Entra nell'albero dei segmenti .

Tradizionalmente, al momento della creazione, costruisci un segmento di albero fino alle sue foglie. Tuttavia, vorremmo nominalmente un albero di segmenti che va da 0-10^9, quindi non c'è assolutamente modo di generare così tanta memoria (e faremmo in tempo a farlo). Tuttavia, cosa succede se creiamo un segmento ad albero, ma per ogni nodo, i suoi figli sono impliciti se non sono mai stati usati. Cioè, non creare nodi figlio se non ci sono elementi in essi . Questa struttura è chiamata, giustamente, l' albero dei segmenti impliciti. L'idea qui è implementare il tuo albero di segmenti normalmente tranne saltare la parte nel costruttore in cui inizializzi i tuoi figli sinistro e destro. Ora, quando devi approfondire i tuoi figli a causa di una query di intervallo parziale, controlla se esistono e, in caso contrario, creali. Altrimenti, poiché non hai mai avuto bisogno di crearli, supponi che la somma dei valori in quei nodi sia 0!

La soluzione finale è la seguente: crea un segmento ad albero del valore massimo interrogabile (se non devi rispondere in modo interattivo, considera di salvare e scansionare le tue query per trovare il valore massimo di r, ma non è necessario). Nota per rendere questo un albero di segmenti implicito . Mantieni l'array di origine dopo ogni aggiornamento e fai anche aggiornamenti puntuali sul tuo albero che saranno O(log(max value)). Le query sono normali query di intervallo di alberi di segmenti, quindi saranno O(log(max value)). Ed eccolo!

1 rootkonda Aug 18 2020 at 03:21

È possibile utilizzare la struttura dei dati basata sulla politica, che ha alcuni metodi utili come order_of_key() - che restituisce un numero di elementi inferiore al num specificato. Possiamo chiamarlo due volte come getcnt(b+1) - getcnt(a) - che fornisce il conteggio degli elementi compresi nell'intervallo specificato. Per maggiori informazioni su questo - puoi fare riferimento -https://codeforces.com/blog/entry/11080e anchehttps://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html

Dopo molte ricerche ho scoperto che questo STL è molto utile durante l'utilizzo di strutture basate su alberi.

Ho testato il codice seguente e supera tutti i casi di test.

#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;
}