Editorial
Con la pubblicazione del nuovo esercizio scavi, colgo l’occasione per pubblicare l’editorial su murale analizzando i suoi vari subtask.
Subtask 1 ( 0 pt)
Nulla di particolare da notare oltre quello già indicato nelle spiegazioni dei vari casi d’esempio nella traccia.
Subtask 2 ( 5 pt)
Il secondo subtask è molto semplice, basta realizzare ogni modifica cosi come ci sono state assegnate.
Complessità: O(N * Q)
#include <bits/stdc++.h>
using namespace std;
void Colora(int N, int Q, vector <int> &A, vector <int> &B, vector <int> &C, vector <int> &murale){
for(int i = 0; i < N; i++){
murale[i] = 0;
}
for(int i = 0; i < Q; i++){
for(int j = A[i]; j <= B[i]; j++){
murale[j] = C[i];
}
}
return;
}
Subtasks 3, 4, 5 (10, 10, 15 pt)
Riprendiamo per un attimo la soluzione del subtask 2, cosa notate? Si riesce facilmente a notare che la modifica che determina la colorazione di una sezione è l’ultima query che la considera. Notato ciò possiamo usufruire delle caratteristiche di questi subtasks, cioè che ogni query ha termine nell’estremo opposto. Quindi per ogni sezione dobbiamo essere in grado di conoscere l’ultima modifica che la riguarda, e uno dei tanti modi per farlo è utilizzare un vettore per i prefissi e uno per i suffissi. Consideriamo per il momento il subtask 3, per ogni query si assegna alla B[i]-esima posizione del vettore dei suffissi l’indice della query. Ora per conoscere la query finale della i-esima sezione non dobbiamo far altro che aggiornare da destra verso sinistra il valore di ogni suffisso. Il valore dell’i-esimo suffisso è il valore massimo tra i-esima posizione e i + 1-esima posizione del suffisso. Per il subtask 4 non dobbiamo far altro che eseguire le stesse operazioni al contrario per i prefissi e nel subtask 5 prendere il valore massimo tra i suffissi e prefissi.
Complessità: O(N + Q)
#include <bits/stdc++.h>
using namespace std;
void Colora(int N, int Q, vector <int> &A, vector <int> &B, vector <int> &C, vector <int> &murale){
// suffissi
vector <int> suffix(N,-1);
for(int i = 0; i < Q; i++){
if(A[i] == 0){
suffix[B[i]] = i;
}
}
for(int i = N - 2; i >= 0; i--){
suffix[i] = max(suffix[i],suffix[i + 1]);
}
// prefissi
vector <int> preffix(N,-1);
for(int i = 0; i < Q; i++){
if(B[i] == N - 1){
preffix[A[i]] = i;
}
}
for(int i = 1; i < N; i++){
preffix[i] = max(preffix[i],preffix[i - 1]);
}
// si prende il valore massimo
for(int i = 0; i < N; i++){
int index = max(suffix[i],preffix[i]);
if(index == -1){
murale[i] = 0;
}else{
murale[i] = C[index];
}
}
}
Subtask 6 (20 pt)
Nel subtask 2 abbiamo notato come solo l’ultima modifica che riguarda l’i-esima sezione ha effetto mentre nei subtasks 3, 4, 5 si è visto come raggiungere una complessità O(N) elaborando solo una volta una sezione; ma come possiamo utilizzare queste osservazioni per risolvere questo subtask? La via più semplice è di modificare il modo con cui elaborare una volta sola le sezioni, trasformando il problema in uno di ricerca e rimozione. La struttura dati che ci aiuta nel nostro scopo è il set che permette ricerca e rimozione di un elemento in tempi logaritmici. Eseguendo le query dall’ultima alla prima cerchiamo il primo elemento utile e lo rimuoviamo fin quando non usciamo dal range della query attuale. Prima di rimuovere l’elemento segniamo il colore alla query.
Complessità: O(N log N + Q)
#include <bits/stdc++.h>
using namespace std;
void Colora(int N, int Q, vector <int> &A, vector <int> &B, vector <int> &C, vector <int> &murale){
for(int i = 0; i < N; i++){
murale[i] = 0;
}
set <int> da_dipingere;
set <int>::iterator it = da_dipingere.begin();
for(int i = 0; i <= N; i++){
da_dipingere.insert(it,i);
}
for(int i = Q - 1; i >= 0; i--){
it = da_dipingere.lower_bound(A[i]);
while((*it) <= B[i]){
murale[*it] = C[i];
it = da_dipingere.erase(it);
}
}
}
Piccola sfida
In quanti modi diversi riuscite a risolvere questo subtask? Io ne ho trovati 4 
Subtask 7 (40 pt)
Eccoci all’ultimo subtask del problema, le osservazioni fondamentali sono sempre le stesse. Cosa bisogna fare rispetto al subtask 6 per ottenere il 100? Bisogna modificare il modo con cui effettuare le operazioni di ricerca e di rimozione. Consideriamo di dover colorare la sezione i, qual’è il successivo da colorare? Potrebbe essere i + 1 oppure il successivo di i + 1 oppure il successivo del successivo del successivo… e cosi proseguendo. In questo modo abbiamo creato un grafo direzionato in cui ogni sezione punta alla prossima da colorare. Per evitare di ripercorre sezioni già visitate, pian piano che visitiamo questo grafo cambiamo la sezione su cui punta quella attuale.
Complessità: O(N log N + Q) con fattori costanti molto più bassi della precedente soluzione.
Provate a scriverlo
Conclusioni
Come vedete, risolvere i piccoli subtask di un problema aiuta nella risoluzione di quello generale. Il problema generale non è altro che l’unione di tutte le sue istante specifiche.
Spero che questo piccolo editorial vi sia piaciuto, per ogni dubbio basta lasciare un piccolo commento e il prima possibile cercherò di rispondervi 
Update:
Ringrazio per la discussione sotto al post, e mi dispiace non essere intervenuto. Mi ha fatto molto piacere vedervi attivi e fornire risposte molto esaustive. Detto ciò mi scuso per l’errore nella complessità per l’ultimo subtask. Mi ricordavo fosse lineare e non logaritmica 
Mi faccio perdonare linkado una pagina che offre molte informazioni sulla struttura dati utilizzata che dovevo confrontare fin dall’inizio dsu