# PBinfo #2051 – pp – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
/*
    prof. Ionel Vasile Pit-Rada
    Complexitate O(N + T)
*/
#include<fstream>
using namespace std;
int c, n, m, a[100005], st[100005], f[100005], b[100005], T, p, q, t, i, x, y, max1, max2, k, z;
long long sp[100005],v,nr;
void sol1(){
    ifstream  fin("pp.in");
    ofstream fout("pp.out");
	fin>>c;
	if(c==1){
		fin>>n;
		v=0;
		for(i=1;i<=n;i++){
			fin>>a[i];
			v=v+a[i];
			sp[i]=v;
		}
		fin>>T;
		for(t=1;t<=T;t++){
			fin>>p>>q;
			fout<<sp[q]-sp[p-1]<<'\n';
		}
	}
	if(c==2){
		fin>>n; m=0;
		for(i=1;i<=n;i++){
			fin>>a[i];
			if(f[a[i]]==0){
				v=f[a[i-1]];
				sp[m]=sp[m-1]+v*(v-1)/2;
				m++; st[m]=i;
			}
			f[a[i]]++;
			b[i]=m;
		}
		v=f[a[n]];
		sp[m]=sp[m-1]+v*(v-1)/2;
		st[m+1]=n+1;
		fin>>T;
		for(t=1;t<=T;t++){
			fin>>p>>q;
			x=b[p]; y=b[q];
			nr=(long long)(q-p+1)*(q-p)/2;
			v=sp[y-1]-sp[x]+(long long)(q-st[y]+1)*(q-st[y])/2+(long long)(st[x+1]-p)*(st[x+1]-p-1)/2;
			nr=nr-v;
			fout<<nr<<'\n';
		}
	}
    fin.close();
    fout.close();
}
int main(){
    sol1();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2051)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2051/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2051/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)