{

Cellulari (IOI 2001)
Copyright (C) 2001 Luca Foschini

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


O(n) query, O(n) update (sufficiente per circa la metà degli input della gara)

Il programma opera nel modo seguente:

Ad ogni richiesta di aggiornamento della casella di coordinate (i,j) viene
sommato ad ogni cella della colonna j , dalla riga i+1 fino a fine colonna
(riga N), il valore A.

Questa modalità di gestione della matrice permette di calcolare in un'unica
operazione la somma dei valori delle celle nell'intervallo [a..b] (a<b) su una
stessa colonna j.Questa somma sarà chiaramente uguale a M[i,b+1]-M[i,a].

Per calcolare quindi la somma dei valori delle celle contenute nel rettangolo
di estremi (L,B)-(R,T) sarà necessario un numero di operazioni proporzionale
alla lunghezza della "base" del rettangolo (R-L+1) e non alla sua "area"
(R-L+1)*(T-B+1)

}

Program Mobiles;

var cmd,N,i,j,x,y,A,S,L,T,R,B:longint;
{
La particolare modalità di gestione della matrice richiede un
sovradimensionamento del numero delle righe (n+1 righe invece di n)
}
   M:array[0..1024,0..1023] of longint; {ogni casella della matrice contiene un integer ma la somma potrebbe non esserlo...}
   
begin
   read(cmd);
   while cmd<>3 do
   begin
      case cmd of
	0 :{inizializza una matrice di N*N celle}
	   begin read(N);for i:= 0 to N do for j:=0 to N-1 do M[i,j]:=0;end;
	1 :{aggiunge al valore di ogni cella della colonna x da y+1 fino a fine colonna (riga N) il valore A}
	   begin read(x);read(y);read(A);
	       for i:= y+1 to N do inc(M[i,x],A);
	    end;
	2 :{calcola il numero di cellulari attivi nei quadrati di coordinate i,j con L<=j<=R, B<=i<=T}
	   begin read(l);read(t);read(r);read(b);
	       S:=0;
	       for i:=l to r do inc(S,M[b+1,i]-M[t,i]);
	       writeln(S);
	    end;
      end; { case }
      read(cmd);
      readln;
   end;
end.