Rezolvare PBinfo #2051

Se consideră un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N]. În legătură cu acest șir de numere ne interesează perechile de poziții (i,j) cu 1≤i<j≤N și a[i]≠a[j] sau ne interesează suma elementelor anumitor secvențe.

Cerința

Se cere să se scrie un program care să citească un număr C reprezentând tipul cerinței, un șir de N numere naturale nenule ordonate crescător a[1]≤a[2]≤...≤a[N] și T perechi de numere naturale (p[k],q[k]) cu 1≤p[k]<q[k]≤N și 1≤k≤T și apoi:

(1) Dacă C=1, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) suma a[p]+a[p+1]+...+a[q].
(2) Dacă C=2, atunci trebuie să se determine pentru fiecare pereche dată de numere naturale (p,q) numărul de perechi (i,j) care respectă simultan condițiile p≤i<j≤q și a[i]≠a[j].

Date de intrare

Fișierul de intrare pp.in conține pe prima linie numărul natural C. Pe al doilea rând se află numărul N. Pe al treilea rând sunt scrise N numere naturale ordonate crescător și separate prin câte un spațiu. Pe al patrulea rând este scris numărul natural T, iar pe fiecare dintre următoarele T rânduri câte două numere naturale separate prin câte un spațiu.

Date de ieșire

Dacă C=1, atunci fișierul de ieșire pp.out va conține pe fiecare dintre primele T linii câte un număr natural. Al k-lea număr va reprezenta suma elementelor cuprinse între pozițiile p[k] și q[k] inclusiv.

Dacă C=2, atunci fișierul de ieșire pp.out va conține pe fiecare dintre primele T linii câte un număr natural. Al k-lea număr va reprezenta numărul cerut de perechi de indici cuprinși între poziţiile p[k] şi q[k] inclusiv.

Restricții și precizări

• 1 ≤ p[i] < q[i] ≤ N ≤ 100 000
• 1 ≤ a[1] ≤ a[2] ≤ ... ≤ a[N] ≤ 100 000
• 1 ≤ T ≤ 1000

Exemplul 1

pp.in

1
5
1 2 3 3 3
2
1 4
2 5

pp.out

9
11

Explicație

Suntem în cazul C=1. Prima pereche (p,q) este (1,4). Suma valorilor din secvență este 1+2+3+3=9. A doua pereche (p,q) este (2,5). Suma valorilor din secvență este 2+3+3+3=11.

Exemplul 2

pp.in

2
5
1 2 3 3 3
2
1 4
2 5

pp.out

5
3

Explicație

Suntem în cazul C=2. Prima pereche (p,q) este (1,4). Perechile de poziții care conțin numere diferite între ele sunt (1,2), (1,3), (1,4), (2,3), (2,4). Deci sunt 5 perechi.

A doua pereche (p,q) este (2,5). Perechile de poziții care conțin numere diferite sunt (2,3), (2,4), (2,5). Deci sunt 3 perechi.