Rezolvare PBinfo #2434

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).

Cerința

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.

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 patru numere A, B, C, D cu semnificația de mai sus, despărțite prin câte un spațiu.

Date de ieșire

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

Restricții și precizări

• 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 ≤ 3000
• Pentru alte 16 puncte: n ≤ 100 000, m ≤ 1000 000 000, q ≤ 100
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru testul din exemplu.

Exemplu:

tnia.in

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

tnia.out

30
6 
5 
0 
6

Explicație

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.