Furnicuţa şi-a construit un depozit pentru grăunţe

Baraj I – Juniori

Problema 3 - PP 100 puncte
Se consideră un şir de N numere naturale nenule ordonate crescător a₁≤a₂≤…≤a_N. În legătură cu acest şir de numere ne interesează perechile de poziţii (i,j) cu 1≤i şi a_i≠a_j sau ne interesează suma elementelor anumitor secvențe.
Cerinţă

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₁≤a₂≤…≤a_N şi T perechi de numere naturale (p_k,q_k) cu 1≤p_kk≤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≤ii≠a_j.

Date de intrare

Fişierul de intrare pp.in conţine pe primul rând 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₁ ≤ a₂ ≤ … ≤ a_N ≤ 100 000
  
• 
  1 ≤ T ≤ 1000
  

Exemplu:

pp.in	pp.out	Explicaţie
1 5 1 2 3 3 3 2 1 4 2 5	9 11	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.
2 5 1 2 3 3 3 2 1 4 2 5	5 3	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.

Limită de timp: 0.1 secunde

Memorie totală: 128 MB