Tnia

tnia

== include(page="template/taskheader" task_id="tnia") ==

Se dă o matrice binară cu $n$ coloane şi $m$ linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la $1$ la $n$, iar liniile sunt numerotate de jos în sus cu valori de la $1$ la $m$. Matricea dată are o formă particulară, astfel că pentru fiecare coloană $i$ de la $1$ la $n$ toate elementele matricei de pe coloana respectivă au valoarea $1$ pentru toate liniile cuprinse în intervalul $[1,h[i]]$ şi în rest valoarea $0$. Valorile $h[i]$ sunt numere naturale date în ordine crescătoare $(h[i-1] ≤ h[i], 1 ≤ i ≤ n)$.
 
h2. Cerinţă
 
Să se răspundă la $q$ întrebări de forma: dându-se numerele $A$, $B$, $C$, $D$ se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colţul stânga-jos în coloana $A$ şi linia $B$, iar colţul dreapta-sus în coloana $C$ şi linia $D$.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare este $tnia.in$.
 
* pe prima linie se găsesc două numere naturale $n$ şi $m$ despărţite printr-un spaţiu, cu semnificaţia de mai sus;
* pe a doua linie sunt cele $n$ elemente $h[i]$ ale vectorului despărţite prin câte un spaţiu;
* pe a treia linie este un număr natural $q$ ce reprezintă numărul de întrebări;
* pe următoarele $q$ linii se găsesc câte $4$ numere $A$, $B$, $C$, $D$ cu semnificaţia de mai sus, despărţite prin câte un spaţiu.

Fişierul de intrare $tnia.in$ ...

h2. Date de ieşire

Fişierul de ieşire $tnia.out$ va conţine $q$ linii reprezentând răspunsul pentru fiecare întrebare.

În fişierul de ieşire $tnia.out$ ...

h2. Restricţii

* $0 ≤ h[i] ≤ m, 1 ≤ n ≤ 100 000$
* $1 ≤ q ≤ 100 000, 1 ≤ m ≤ 1 000 000 000$
* Pentru $15$ puncte: $n, m, q ≤ 100$
* Pentru alte $16$ puncte: $n, m, q ≤ 3 000$
* Pentru alte $16$ puncte: $n ≤ 100 000, m ≤ 1 000 000 000, q ≤ 100$
* Conform regulamentului OJI, se vor acorda $10$ puncte pentru exemplu.

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. tnia.in |_. tnia.out |_. Explicaţie |
|5 10
2 3 7 8 10
5
1 1 5 10
2 5 4 7
3 2 3 6
3 8 3 10
3 2 3 10
|30
6
5
0
6
|Zona dreptunghiulară având colţul stânga-jos la coloana $1$ şi linia $1$ şi colţul dreapta-sus la coloana $5$ şi linia $10$ are suma elementelor $30$.
Analog, pentru celelalte patru întrebări, răspunsurile corecte sunt: $6$, $5$, $0$ şi $6$.
|

table(example). |_. tnia.in |_. tnia.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
...

== include(page="template/taskfooter" task_id="tnia") ==