Dopo i casi di klavir e coats mi sono reso conto di sapere poco o nulla di probabilità e combinatoria, almeno sul campo informatico.
Su SPOJ abbiamo la categoria probability-theory… è sufficiente? Cosa aggiungereste?
Altra cosa in cui mi piacerebbe migliorare sono query 2D/3D. In particolare, ancora non ho capito come returnare la somma di una regione sapendo di poter settare una riga o una colonna e sapendo che la dimensione H \times V è proibitiva in quanto a complessità temporale e spaziale).
Un esempio più complesso di quanto intendo è IOPC1207 (che ancora non ho capito come risolvere, se ci fosse un’anima pia disponibile 
), ma anche un paio di problemi delle COCI di Dicembre (quello della matrice in cui c’erano query di set riga e colonna e bisognava ottenere la somma modulo 10^9 + 7).
Infine… algoritmi per ricerca completa tipo iterative dfs, A*, IDA*, e approcci come ricerca con pruning, branch and bound, MITM? Che problemi suggerireste, fornendo una scala di difficoltà da “quasi nabbo” a “IOIsta”? E soprattutto, nel competitive programming quanto vi sono stati utili?
Il problema che hai linkato è molto carino, così su due piedi ti direi che puoi risolverlo mantenendo per ognuna delle 3 dimensioni gli indici di quelle accese (tre segment tree con lazy propagation andranno benissimo).
Per contare i cubi accesi in una data regione, li conti separatamente contando prima quelli accesi grazie al loro indice in una determinata dimensione.
Dopo che hai contato quelli in una dimensione, puoi contare quelli accesi per le altre due con il piccolo accorgimento di non contare due volte le posizioni già considerate.
Diciamo che il problema di fondo era che non avevo idea di cosa fosse un 2D segment sum 
(e pertanto un 3D); conoscevo solo o il vettore di segment tree (con complessità O(\min(H,V)\log \max(H,V)) temporale) e il quad tree e che ha complessità O(N) nel caso peggiore \implies praticamente inutile.
il commento che tu hai detto l’ho letto decine di volte un po’ dappertutto, quindi posso dirti che hai detto bene.
A questo punto, mi sento in voga di condividere a mo’ di diario giornaliero, utile ai posteri:
- in questo video l’argomento del 2D segment tree l’argomento è spiegato relativamente bene.
L’idea è di usare un segment tree di segment tree.
In particolare, se supponiamo ad esempio di fare un segment tree di ogni riga gestiamo il “join” di due nodi come un tree che abbia come nodi la somma dei nodi rispettivi quindi se ad esempio abbiamo le righe [1,2,3,4] e [5,6,7,8] avremo i rispettivi alberi
a1 = [10, 3, 7, 1, 2, 3, 4]
a2 = [26, 11, 15, 5, 6, 7, 8]
e dunque
join(a1, a2) = [36, 14, 22, 6, 8, 10, 12]; per maggiori informazioni guardate il video e la descrizione (compaiono un listato che mette in pratica quanto detto e qualche problema su codeforces… ne aggiungo uno io che è fondamentalmente implementazione di quanto appena detto).
lascio sempre ai posteri una riflessione su come implementare la lazy per rispondere a update di rettangoli.
La lazy propagation in un segment tree di segment tree non funziona (per quanto riguarda le RMQ), almeno non in O(log^2N) per update/query 
Comunque in un segment tree k-D hai complessità O(log^kN) per query, quindi nel problema linkato credo che anche con una buona implementazione potresti uscire facilmente fuori dai tempi e non era quella la soluzione prevista.
1 Mi Piace
I know però mi riferivo al fatto che ancora non avevo studiato i 2D segment tree… ora lo conosco e vedrò di trarne giovamento se mai mi servirà.
Tornando a IOPC1207:
l’algoritmo da quanto ho capito dovrebbe fare questo:
- Tengo 3 alberi lazy, uno per ogni asse.
- Per ogni update del tipo
flip(axis,a,b) inverto i bit mediante lazy_segtree[axis].update_flip(a,b)
- Per ogni query del tipo
query(x1,y1,z1,x2,y2,z2):
- sia
r0 = lazy_segtree[0].query(x1,x2) e similmente per r1 e r2
- sia
g0 = (x2-x1+1) - r0 (e similmente per g1 e g2)
- la soluzione è
r0*r1*r2 + r0*g1*g2 + g0*r1*g2 + g0*g1*r2
Ora la domanda è: perché r0*r1*r2 + r0*g1*g2 + g0*r1*g2 + g0*g1*r2?
Qualcuno potrebbe spiegarmi questo?
Per capirlo meglio, ti consiglio di risolvere prima lo stesso problema però nella variante 2D 
(e pertanto un 3D); conoscevo solo o il vettore di segment tree (con complessità 
