Credevo bastasse usare semplicemente le list del C++ e invece va in timeout. Ho pure utilizzato una variabile che tenesse conto dell’ultima posizione puntata dall’iterator così da accorciare i tempi della funzione advance() passandogli come parametro di avanzamento un “delta pos” eppure va ancora in timeout!
Che complessità hai attualmente in ricerca ed update?
Prova a ragionare su una possibile soluzione che abbia tempo di ricerca e di update uguali. Indizio: O(√n).
Segment tree?
Mmm… in tal caso sarebbe facilmente generalizzabile e avrei detto O(log n).
Parti dalla soluzione banale O(n) update e O(1) ricerca, ovvero tieni l’array e ogni volta che lo modifichi sposti tutti gli elementi da spostare.
Da lì, cerca un modo di ridurre la complessità di update a discapito della ricerca.
Qualche aiutino in più?
Ok, abbiamo detto che per adesso mantieni un array S di lunghezza N con i valori su cui devi fare le operazioni.
Dato che O(sqrt(N)), direi che l’array N va diviso in sqrt(N) parti, lunghe ciascuna sqrt(N). In pratica si utilizza la sqrt-decomposition. Ora resta solo da capire come effettuare le operazioni 
Parti dall’operazione “c”. Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell’array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)).
Sono riuscito, grazie mille per l’aiuto 
L’approccio per vasi2 è lo stesso? Anche se penso che sia improbabile, io lo chiedo lo stesso
Io mi ci sono messo appena 20 minuti fa a fare vasi1, però non ho ancora capito come fare l’update con la sqrt decomposition.
C’è un container delle STL in particolare che ti può dare una (grossa) mano
Immagino ti riferisca alle liste. Stavo finendo di implementarle che sono dovuto uscire di casa!
Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)).Ma se io divido l'array in sqrt(N) array lunghi sqrt(N) ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' i-esimo valore, Se io so che concatenando gli sqrt(N) ottengo l'array, per ricercare l'elemento i non basta accedere alla (i / sqrt(N)) parte alla (i % sqrt(N)) posizione?wil93
Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)).Ma se io divido l'array in sqrt(N) array lunghi sqrt(N) ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' i-esimo valore, Se io so che concatenando gli sqrt(N) ottengo l'array, per ricercare l'elemento i non basta accedere alla (i / sqrt(N)) parte alla (i % sqrt(N)) posizione?wil93
Forse mi sono perso qualcosa nel ragionamento.simone.pri
Io l'ho risolto nella stessa maniera ma usando le deque, dato che la lettura è costante mentre nelle liste è lineare (confermate?)Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)).Ma se io divido l'array in sqrt(N) array lunghi sqrt(N) ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' i-esimo valore, Se io so che concatenando gli sqrt(N) ottengo l'array, per ricercare l'elemento i non basta accedere alla (i / sqrt(N)) parte alla (i % sqrt(N)) posizione?wil93
Forse mi sono perso qualcosa nel ragionamento.simone.pri
Invece è corretto, perché non dovrebbe esserlo?Lawliet
Vero, infatti anch’io mi sono reso conto che con le deque è più veloce. Soprattutto per le operazioni di push/pop_back/front che sono in O(1). Solo che nonostante questo non riesco ad andare oltre come punteggio. Prende tutti gli input fino al penultimo del secondo subtask.
Allora perchè la ricerca dovrebbe avere complessità O(N/M) + O(M) ??Parti dall'operazione "c". Chiaramente peggiorerà (prima era O(1) per via della semplice indicizzazione dell'array). Comunque dovrebbe essere facile trovare come farla in O(N/M) + O(M) = O(sqrt(N)).Ma se io divido l'array in sqrt(N) array lunghi sqrt(N) ognuno, dato che la richiesta del problema non è di trovare un valore in particolare ma di trovare l' i-esimo valore, Se io so che concatenando gli sqrt(N) ottengo l'array, per ricercare l'elemento i non basta accedere alla (i / sqrt(N)) parte alla (i % sqrt(N)) posizione?wil93
Forse mi sono perso qualcosa nel ragionamento.simone.pri
Invece è corretto, perché non dovrebbe esserlo?Lawliet
Sostanzialmente non dovresti usare remove e search ma le funzioni per aggiungere e togliere valori dalla fine è dll’inizio della lista (push_back(), push_front(), pop_back(), pop_front()) per tutte le liste “centrali” tra i due indici coinvolti nell’update. Per i segmenti che invece contengono questi due indici devi usare remove e insert. Il problema è che le liste sono lente, quindi ti conviene usare varie deque.
Sostanzialmente non dovresti usare remove e search ma le funzioni per aggiungere e togliere valori dalla fine è dll'inizio della lista (push_back(), push_front(), pop_back(), pop_front()) per tutte le liste "centrali" tra i due indici coinvolti nell'update. Per i segmenti che invece contengono questi due indici devi usare remove e insert. Il problema è che le liste sono lente, quindi ti conviene usare varie deque.Esatto, dato che pop/push_back e pop/push_front hanno coplessità costante (O(1)). Quindi ti fai un vettore di sqrt(N) deque, ognuna con sqrt(N) elementi (o meno, nel caso dell'ultima, dato che sqrt(N) non è sempre un intero).La complessità migliora perché tu fai solo 2 operazioni per ogni segmento, diventando quindi O(2*sqrt(N))=O(sqrt(N)).Non so se sono stato chiaroLawliet