Cod sursa(job #993966)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 4 septembrie 2013 19:49:14
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");

int n, aib[100005], m;
inline int zero(int &x) { return x & -x;}

inline void update(int poz, int value)
{
    while (poz<=n) aib[poz]+=value, poz+=zero(poz);
}

inline int query(int poz)
{
    int ans=0;
    while (poz) ans+=aib[poz], poz-=zero(poz);
    return ans;
}
int main()
{
    int x; f>>n>>m;
    for (int i=1; i<=n; i++) f>>x, update(i, x);

    for (int i=1; i<=m; i++)
    {
        int tip; f>>tip;
        if (tip==0)
        {
            int pos, val; f>>pos>>val;
            update(pos, val);
        }
        else if (tip==1)
        {
            int left, right; f>>left>>right;
            g<<query(right)-query(left-1)<<'\n';
        }
        else
        {
            int x, q, ans=0; f>>x; q=x;
            for (int i=1<<16; i>0; i>>=1)
               if (i+ans<=n && aib[ans+i]<x) x-=aib[ans+i], ans+=i;
            ++ans;
            if (ans!=-1 && query(ans)!=q) ans=-1;
            g<<ans<<'\n';
        }
    }
    return 0;
}