/* Mobiles (IOI 2001) Copyright (C) 2001-2002 Paolo Boldi and Sebastiano Vigna This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA (Come per tutti i problemi del 2001, è utile leggere il libretto distribuito dagli organizzatori, e disponibile nella sezione "Materiale didattico" della home page http://ioi.dsi.unimi.it/.) Questo problema è stato chiaramente progettato per non essere risolto completamente. Gli autori volevano costringere i gareggianti a tirare fuori le armi più potenti del loro arsenale algoritmico: l'unica soluzione funzionante entro i limiti previsti (e mostrata in questo programma) è basata su una struttura dati molto sofisticata descritta da P.M. Fenwick in un articolo apparso su Software--Practice and Experience, vol. 24, n. 3, pag. 327-336, 1994, dal titolo "A new data structure for cumulative frequency tables", che ha fornito lo spunto. L'idea, semplice quanto diabolica, è facile da descrivere su un intervallo, cioè in dimensione 1. Abbiamo quindi istruzioni per modificare il numero di cellulari in un elemento dell'intervallo, e istruzioni per chiedere il numero di cellulari in un dato sottointervallo. Se il numero di celle nell'intervallo è S, utilizziamo un vettore c di lunghezza S. Invece però di tenere in c[i] il numero di cellulari correntemente nella cella di indice i, teniamo il numero di cellulari presenti nell'intervallo che va da c[i] alla cella con indice ottenuto mettendo a 1 le cifre che formano il suffisso massimale composto da zeri nell'espansione binaria di i (se i=0, l'altro estremo è S-1). Per fissare le idee, assumiamo S=8. Allora c[0] contiene il numero di cellulari nell'intero intervallo, c[4] il numero di cellulari nella seconda metà dell'intervallo, c[2] il numero di cellulari nel secondo quarto dell'intervallo, c[6] il numero di cellulari nell'ultimo quarto dell'intervallo e c[i], dove i è dispari, il numero di cellulari nella cella di indice i (dato che il suffisso massimale formato da zeri nell'espansione binaria di i è vuoto in questo caso). Innanzitutto notiamo che il numero di elementi da aggiornare quando varia il numero di cellulari in una cella è logaritmico nella lunghezza dell'intervallo. Inoltre è molto facile scoprire quali sono gli indici da aggiornare quando varia il numero di cellulari in i: basta cancellare uno a uno i bit a uno nell'espansione binaria di i. Per esempio, quando varia il numero di elementi nella cella di indice 7 (111 in binario) bisogna aggiornare la cella di indice 7, la cella di indice 6 (110), 4 (100) e 0 (000), mentre se cambia il numero di cellulari nella cella di indice 5 (101) bisogna aggiornare la cella di indice 5, la cella di indice 4 (100) e la cella di indice 0 (000). Infine, sempre con un numero logaritmico di accessi è possibile calcolare il numero di cellulari in un intervallo con estremo destro in S-1, diciamo [i,S-1]. Infatti c[i] fornisce il numero di cellulari presenti dalla cella i fino alla cella con indice ottenuto mettendo a 1 le cifre che formano il suffisso massimale composto da zeri nell'espansione binaria di i. A questo punto basta sommare 1, ottenendo così una nuova cella che contiene un'altra somma. Si continua così sino a eccedere S. Notate che a ogni passo l'intervallo coperto da una cella raddoppia, e quindi la sommatoria comprende un numero logaritmico di addendi. Per sapere il numero di cellulari in un intervallo generico [i,j] basta ovviamente calcolare il numero di cellulari in [i,S-1] e sottragli quello in [j+1,S-1]. Per passare in dimensione due basta stipulare che la cella di indice [i,j] contiene il numero di cellulari in un rettangolo che ha ampiezza sulle ascisse e sulle ordinate calcolate utilizzando il suffisso massimale di zeri di i e j, rispettivamente. Sia l'aggiornamento che le richieste sono ora dell'ordine del quadrato del logaritmo di S. Notate che soluzioni con un diverso bilanciamento (per esempio, quella banale, che ha aggiornamento in tempo costante e richieste in tempo quadratico) non potevano funzionare, perché delle 60000 istruzioni possibili in un'esecuzione non era dato sapere quante fossero aggiornamenti e quante richieste. */ #include #include #include #include #include #include typedef struct { int x,y; } punto; typedef struct { int x1, /* min x */ x2, /* max x */ y1, /* min y */ y2; /* max y */ } rett; FILE *Fin, *Fout; #define MAXS 1024 int c[MAXS][MAXS]; /* La matrice contenente le somme parziali */ int s[12] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 }; /* Potenze di 2 precomputate */ int S, logS; /* Questa funzione aggiorna la matrice delle somme parziali secondo l'incremento incr nel punto p. Si tratta di due cicli annidati che cancellano via via gli uni dalla rappresentazione binaria delle coordinate del punto. */ void aggiorna(punto p, int incr) { int i,j,x,y; x = p.x; i=0; do { j = 0; y = p.y; do { c[x][y] += incr; for(; !(s[j] & y) && j <= logS; j++); y ^= s[j]; } while( j <= logS ); for(; !(s[i] & x) && i <= logS; i++); x ^= s[i]; } while( i <= logS ); } /* Questa funzione restituisce la prossima cella da sommare quando si sta richiedendo il numero di cellulari in un rettangolo. Concettualmente, si tratta di riempire di uni il massimo suffisso di zeri di x e poi sommare uno. In pratica, basta cercare il primo bit a uno (da destra) nell'espansione binaria di x e sommarne un'altro nella stessa posizione. */ __inline int pross(int x) { int i; if (x == 0) return S; for(i=0; i<=logS; i++) if ( s[i] & x ) return x += s[i]; } /* Questa funzione calcola il numero di cellulari nel rettangolo cha ha estremi e . */ __inline int conta2(int x1, int y1) { int res=0, x, y; for(x=x1; x utilizzando il principio di inclusione/esclusione. */ __inline int conta(rett r) { return conta2(r.x1, r.y1) + conta2(r.x2+1, r.y2+1) - conta2(r.x1, r.y2+1) - conta2(r.x2+1, r.y1); } int main(int argc, char *argv[]) { int istr, a; punto p; rett r; Fin = stdin; Fout = stdout; for(;;) { fscanf(Fin, "%d", &istr); if (istr == 3) break; if (istr == 0) { fscanf(Fin, "%d", &S); for(logS=0; s[logS] < S; logS++); } else if (istr == 1) { fscanf(Fin, "%d %d %d", &p.x, &p.y, &a); aggiorna(p, a); } else { fscanf(Fin, "%d %d %d %d", &r.x1, &r.y1, &r.x2, &r.y2); fprintf(Fout, "%d\n", conta(r)); } } return 0; }