Cod sursa(job #2764777)

Utilizator GligarEsterabadeyan Hadi Gligar Data 22 iulie 2021 16:44:31
Problema Arbori indexati binar Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>

using namespace std;

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

const int nmax=100000, n2max=(1<<17);

int v[2*n2max];

int solutie(int a, int b, int nod, int l, int r){
    if(a>r||b<l){
        return 0;
    }else if(a<=l&&r<=b){
        return v[nod];
    }else{
        int x=solutie(a, b, nod*2 ,l ,(l+r)/2);
        int y=solutie(a, b, nod*2+1, (l+r)/2+1, r);
        return x+y;
    }
}

int solutie2(int nod, int l, int r, int s){
    if(l==r){
        if(v[nod]==s){
            return nod;
        }else{
            return -1;
        }
    }else if(s<=v[nod*2]){
        return solutie2(nod*2, l, (l+r)/2, s);
    }else{
        return solutie2(nod*2+1, (l+r)/2+1, r, s-v[nod*2]);
    }
}

int main(){
    int n,m;
    fin>>n>>m;
    int n2=1;
    while(n2<n){
        n2*=2;
    }
    for(int i=1;i<=n;i++){
        fin>>v[n2+i-1];
    }
    for(int i=n2-1;i>=1;i--){
        v[i]=v[i*2]+v[i*2+1];
    }
    for(int i=1;i<=m;i++){
        int k,a,b;
        fin>>k;
        if(k==0){
            fin>>a>>b;
            v[n2+a-1]+=b;
            for(int x=(n2+a-1)/2;x>0;x/=2){
                v[x]=v[x*2]+v[x*2+1];
            }
        }else if(k==1){
            fin>>a>>b;
            fout<<solutie(a,b,1,1,n2)<<"\n";
        }else{
            fin>>a;
            fout<<solutie2(1,1,n,a)-n2+1<<"\n";
        }
    }
    return 0;
}