# Cod sursa(job #2757130)

Utilizator Data 3 iunie 2021 23:37:12 Distincte 25 cpp-64 done Arhiva de probleme 6.89 kb
``````/*
S-ar putea sa fie nevoie de long long
*/

#include <iostream>
#include <fstream>

#define NMAX 100000

using namespace std;

ifstream fin ("distincte.in");
ofstream fout ("distincte.out");

int *tree[4 * NMAX + 1];
int lg[4 * NMAX + 1];
int lgQuery[4 * NMAX + 1];
int v[NMAX + 1];
int A, B;

int dimensiuneInterclasare(int *a, int *b, int dim1, int dim2){
int i = 0, j = 0;
int ct = 0;
while(i < dim1 && j < dim2){ //indexat de la 0
if(a[i] < b[j]){
i++;
}
else if(a[i] > b[j]){
j++;
}

else {
//egalitate
while(j < dim2 && a[i] == b[j]){
j++;
}

i++;
while(i < dim1 && a[i] == a[i - 1]){
i++;
}
}

ct++;
}

for(int k = i; k < dim1; k++){
if( !(k > 0 && a[k] == a[k - 1] ) ){
ct++;
}
}

for(int k = j; k < dim2; k++){
if( !(k > 0 && b[k] == b[k - 1] ) ){
ct++;
}
}

return ct;
}

inline void interclasare(int * (&dest), int * (&a), int * (&b), int dim1, int dim2){
int i = 0, j = 0;
int ct = 0;
while(i < dim1 && j < dim2){ //indexat de la 0
if(a[i] < b[j]){
dest[ct] = a[i];
i++;
}
else if(a[i] > b[j]){
dest[ct] = b[j];
j++;
}

else {
//egalitate
dest[ct] = a[i];
while(j < dim2 && a[i] == b[j]){
j++;
}

i++;
while(i < dim1 && a[i] == a[i - 1]){
i++;
}
}

ct++;
}

for(int k = i; k < dim1; k++){
if(k == 0){
dest[ct] = a[k];
ct++;
}
else {
if(a[k] != a[k - 1]){
dest[ct] = a[k];
ct++;
}
}
}

for(int k = j; k < dim2; k++){
if(k == 0){
dest[ct] = b[k];
ct++;
}
else {
if(b[k] != b[k - 1]){
dest[ct] = b[k];
ct++;
}
}
}
}

void afisare(int *v, int dim){
for(int i = 0; i < dim; i++){
cout << v[i] << ' ';
}
cout << "\n";
}

void buildArbore(int node, int left, int right){
if(left == right){
tree[node] = (int *) malloc(sizeof(int));
tree[node][0] = v[left];
lg[node] = 1;
return;
}

int mid = left + (right - left) / 2;
buildArbore(node * 2, left, mid);
buildArbore(node * 2 + 1, mid + 1, right);

//interclasez tree[node * 2] si tree[node * 2 + 1] in tree[node];

//rulez o simulare a interclasarii sa vad ce dimensiune o sa aiba
//ca sa stiu cat sa declar
lg[node] = dimensiuneInterclasare(tree[node * 2], tree[node * 2 + 1], lg[node * 2], lg[node * 2 + 1]);
int aux = lg[node];

tree[node] = (int *) malloc( aux * sizeof(int) );

interclasare(tree[node], tree[node * 2], tree[node * 2 + 1], lg[node * 2], lg[node * 2 + 1]);

/*
printf("( %d, %d )\n", left, right);
afisare(tree[node], lg[node]);

printf("\n");
*/
}

int * query(int node, int left, int right){
//printf("Incep query (%d, %d, %d)\n", node, left, right);

if(A <= left && right <= B){
//intervalul e complet inclus
lgQuery[node] = lg[node];
int * frunza = (int *) malloc( (lgQuery[node]) * sizeof(int) );

for(int i = 0; i < lg[node]; i++){
frunza[i] = tree[node][i];
}

//printf("In intervalul [%d, %d] e cuprins intreg [%d, %d] si arata ca:", A, B, left, right);
//afisare(frunza, lgQuery[node]);
//printf("\n");

return frunza;
}

int mid = left + (right - left) / 2;
int *rez1, *rez2;
int OK1 = 0, OK2 = 0;
if(A <= mid){
OK1 = 1;
rez1 = query(node * 2, left, mid);
}
if(B >= mid + 1){
OK2 = 1;
rez2 = query(node * 2 + 1, mid + 1, right);
}

if(OK1 == 0){ //adica rez2 trb
lgQuery[node] = lgQuery[node * 2 + 1];
//printf("Termin query (%d, %d, %d)\n", node, left, right);
return rez2;
}
else if(OK2 == 0){ //adica rez1 trb
lgQuery[node] = lgQuery[node * 2];
//printf("Termin query (%d, %d, %d)\n", node, left, right);
return rez1;
}

else {
//printf("Ajung in egalitate de OK-uri!\n");

//se afla ceva in ambii fii
//deci interclasez rezultatele din ambii fii
lgQuery[node] = dimensiuneInterclasare(rez1, rez2, lgQuery[node * 2], lgQuery[node * 2 + 1]);

//printf("lgQuery a terminat de calculat\n");
//afisare(rez1, lgQuery[node * 2]);
//afisare(rez2, lgQuery[node * 2 + 1]);
//printf("lgQuery[ %d ] = %d\n", node, lgQuery[node]);

int * REZ = (int *) malloc( (lg[node]) * sizeof(int) );
interclasare(REZ, rez1, rez2, lgQuery[node * 2], lgQuery[node * 2 + 1]);

///dupa ce i-am interclasat pot sa ii sterg pe rez1 si rez2 !!!!
///altfel consum o gramada de memorie degeaba
free(rez1);
free(rez2);

//printf("Termin egalitatea de OK-uri!\n");

//printf("Termin query (%d, %d, %d)\n", node, left, right);
return REZ;
}
}

/*
void curatareArbore(int node, int left, int right){
free(treeQuery[node]);

if(left == right){ //ca sa nu ies din limitele memoriei
return;
}

int mid = left + (right - left) / 2;

if( trebuieSterg[node * 2] ){
curatareArbore(node * 2, left, mid);
}
if( trebuieSterg[node * 2 + 1] ){
curatareArbore(node * 2 + 1, mid + 1, right);
}
}
*/

int main()
{
int N, K, M;
fin >> N >> K >> M;

for(int i = 1; i <= N; i++){
fin >> v[i];
}

/*
for(int i = 1; i <= N; i++){
printf("v[ %d ] = %d\n", i, v[i]);
}
printf("\n");
*/

buildArbore(1, 1, N);

for(int q = 1; q <= M; q++){
//printf("Incep raspunsul %d\n", q);
fin >> A >> B;

//cout << "\n";

int * raspuns = query(1, 1, N);
//calculez suma celor din *raspuns
//nu imi adauga complexitate in plus pt ca oricum am facut interclasari pe 2 siruri care sa mi-l dea pe asta
//deci deja am facut pasi in plus asa ca nu am ce sa optimizez aici
int suma = 0;
for(int j = 0; j < lgQuery[1]; j++){ //lgQuery[1] = dimensiunea lui *raspuns;
suma = suma + raspuns[j];
}

fout << suma << "\n";

//printf("Gata raspunsul %d\n\n", q);
//free(raspuns);

//afisare(raspuns, lgQuery[1]);
//cout << "\n\n\n\n\n\n\n";
}

return 0;
}
``````