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
șim
despărțite printr-un spațiu, cu semnificația de mai sus; - pe a doua linie sunt cele
n
elementeh[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 numereA
,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
.