. I need use Long Double because I will use very large numbers. This is the problem(Spanish) RSQ and this is my code:Excuse me my poor english.
Code: Select all
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <fstream>
using namespace std;
long long int n;
void inicializar(long long int nodo, unsigned long long int ind_izq,unsigned long long int ind_der, double M[], double arreglo[]);
double consulta(long long int nodo, unsigned long long int ind_izq, unsigned long long int ind_der, double M[], double arreglo[], unsigned long long int i, unsigned long long int j);
void set(long long int nodo,unsigned long long int ind_izq, unsigned long long int ind_der, double M[],double arreglo[], long long int valor, unsigned long long int indice);
int main()
{
long long int op1, op2;
string orden;
cin >> n;
double vector[n];
//CALCULAMOS LA CANTIDAD DE NODOS QUE TENDRA EL ARBOL SEGMENTADO
unsigned long long int cant_nodos=n*2+1;
unsigned long long int a=0, j=1;
while(cant_nodos>a){
a+=j;
j=j<<1;
}
cant_nodos=a;
//VECTOR QUE CONTENDRA LOS VALORES DEL ARBOL SEGMENTADO
double aux[cant_nodos];
for(long long int i=0; i<n; i++){
cin >> vector[i];
}
//INICIALIZAMOS NUESTRO ARBOL SEGEMENTADO-CORRECTO
inicializar(1,0,n-1,aux,vector);
while(cin >> orden >> op1 >> op2){
if(orden=="set"){
long long int diff=op2-vector[op1-1];
vector[op1-1]=op2;
set(1,0,n-1,aux,vector,diff,op1-1);
}
else{
double resultado=(double)consulta(1,0,n-1,aux,vector, op1-1, op2-1);
//EVITAMOS LA EXPONENCIACION
cout << fixed << setprecision(0) << resultado << endl;
}
}
return 0;
}
//nodo=nodo en el que estamos; ind_izq=rango izquierdo; ind_der=rango derecho; M=matriz que tiene el indice del menor elemento de cada nodo
void inicializar(long long int nodo, unsigned long long int ind_izq, unsigned long long int ind_der, double M[], double arreglo[]){
//SI ESTAMOS EN EL MISMO NODO LE COLOCAMOS EL VALOR DEL INDICE DERECHO O IZQUIERDO
if(ind_izq==ind_der){
M[nodo]=(double)arreglo[ind_izq];
}else{
//CALCULO DE LOS VALORES EN EL LADO DERECHO Y IZQUEIRDO
//DERECHO
inicializar(nodo*2, ind_izq, (ind_der+ind_izq)/2, M, arreglo);
//IZQUIERDO
inicializar(nodo*2+1, (ind_der+ind_izq)/2+1, ind_der, M, arreglo);
//BUSCAMOS CUAL ES EL MENOR VALOR
//PARA ESO COMPARAMOS EL VALOR DE LOS DOS NODOS IJOS
M[nodo]=(double)M[nodo*2]+M[nodo*2+1];
}
}
double consulta(long long int nodo, unsigned long long int ind_izq, unsigned long long int ind_der, double M[], double arreglo[], unsigned long long int i, unsigned long long int j){
double p1,p2;
//DEVUELVE 0 SI ESE NODO NO ES PARTE DEL RANGO BUSCADO
if(i>ind_der || j<ind_izq)return 0;
//DEVUELVE EL VALOR DEL NODO SI ESTE ES PARTE DEL RANGO
if(ind_izq >=i && ind_der<=j)return M[nodo];
//P1 CONSULTA LOS NODOS DE LA IZQUIERDA Y P2 LOS NODOS DE LA DERECHA
p1=(double)consulta(2*nodo,ind_izq,(ind_izq+ind_der)/2,M,arreglo,i,j);
p2=(double)consulta(2*nodo+1,(ind_izq+ind_der)/2+1,ind_der,M,arreglo,i,j);
//SI P1 ES -1, SIGNIFICA QUE EL NODO P2 ES EL UNICO QUE ESTA EN EL RANGO BUSCADO POR LO TANTO LOD EVUELVE
return p1+p2;
}
void set(long long int nodo, unsigned long long int ind_izq, unsigned long long int ind_der, double M[],double arreglo[],long long int valor, unsigned long long int indice){
//COMPROBAMOS QUE EL INDICE DEL ELEMENTO A CAMBIAR SEA PARTE DE LOS RANGOS DEL NODO ACTUAL
//SI NO ES PARTE DEL RANGO
if(indice<ind_izq || indice>ind_der)return;
if(ind_izq==indice && ind_der==indice){
M[nodo]=(double)arreglo[indice];
return;
}
//SI ESTA EN EL RANGO LE AUMENTAMOS EL VALOR, EL VALOR YA HA SIDO CALCULADO COMO AL DIFERENCIA ENTRE EL NUMERO ANTERIOR Y EL ACTUAL
M[nodo]=(double)M[nodo]+valor;
//LLAMAMOS A SET PARA EL NODO DE LA DERECHA Y EL DE LA IZUQIERDA
//UPDATE ANODO DE LA IZQUIERDA
set(nodo*2,ind_izq,(ind_izq+ind_der)/2,M, arreglo,valor, indice);
//UPDATE A NODO DE LA DERECHA
set((nodo*2)+1,((ind_izq+ind_der)/2)+1,ind_der,M, arreglo, valor, indice);
}