Per il secondo problema della rubrica TAI vi proponiamo murale, riuscirete a trovare la colorazione finale in tempo? 
In ogni caso, da oggi i problemi avranno il 100% in più di logo rispetto a prima! Ed è un incremento spaziale. Il logo (purtroppo) è stato realizzato da me, con le migliori tecnologie disponibili (tipo paint e gimp) per ottenere un risultato (non) formidabile. Puntiamo col passare del tempo a migliorarlo, come la qualità degli esercizi della rubrica.
Tra circa due settimane verrà caricato un editorial e un nuovo esercizio. Saremo ben felici di condividere e commentare le soluzioni con tutti voi.
Have fun 
3 Mi Piace
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
3 Mi Piace
Ciao, ho trovato una soluzione basata su ufds con complessità (N+Q)*ack_inv(N) ma non riesco a trovare nessuna soluzione N+Q, puoi darmi un indirizzo? Grazie
fai le ufds cosi
oppure dici che ack_inv(N) e’ abbastanza piccolo da considerarlo O(1), tanto solo tarjan capisce quella complessita
3 Mi Piace
Grazie per la risposta, quindi se ho capito bene la mia soluzione (che devo ancora scrivere xD) ha in realtà complessità N+Q? Se sì sapresti spiegarmi brevemente il perché dato che non ci ho capito molto dal paper.
Prova a vedere quanto cresce velocemente la funzione di ackermann e quanto cresce lentamente la sua inversa, ti convincerai che non cambia molto da O(N+Q)
Scusa ma non ho capito, stai assumendo che ack_inv(N) = O(1)?
1 Mi Piace
Comunque la union-find standard con solo la path compression ha complessità logaritmica, aggiungendo anche la union by rank diventa \alpha (N).
2 Mi Piace
Quell’uguaglianza è sbagliata teoricamente, ma nella pratica la differenza è praticamente invisibile.
Quindi, dimmi se sbaglio, la complessità corretta non è N+Q ma (N+Q)*ack_inv(N)?
1 Mi Piace
Sì, comunque ribadisco che è un fattore invisibile nella pratica, infatti spesso viene ignorato, per esempio nel Tarjan’s offline lowest common ancestor viene spesso omesso.
1 Mi Piace
Tanto per fare un esempio di quanto cresce piano α(n), nella pratica si assume sempre minore di 5, cito wikipedia
In fact, α(n) is less than 5 for any practical input size n, since A(4, 4) is on the order of
1 Mi Piace
Buongiorno, vorrei notificarvi di un errore nel testo di murale. La funzione da definire è
void Colora(int N, int Q, vector <int> &A, vector <int> &B, vector <int> &C, vector <int> &murale);
ma nel testo c’è scritto questo (manca una , e una &):
void Colora(int N, int Q, vector <int> &A, vector <int> B, vector <int> &C vector <int> &murale);
1 Mi Piace
Grazie, aggiusterò il prima possibile.
Murale si può risolvere anche con una specie di lazy propagation su un segment tree, probabilmente è una soluzione più complessa del necessario ma è la prima cosa che mi è venuta in mente. La complessità è O(Q*log(N) + N).