Cod sursa(job #2175407)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 16 martie 2018 17:01:26
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

#define NMAX 100005
#define lsb(x) ((-x) & (x))

int N, M, aib[NMAX], tip, x, y;

void update(int pos, int value) {
    while (pos <= N) {
        aib[pos] += value;
        pos += lsb(pos);
    }
}

int query(int pos) {
    int res = 0;
    while (pos) {
        res += aib[pos];
        pos -= lsb(pos);
    }

    return res;
}

int main() {
    f >> N >> M;
    for (int i = 1; i <= N; ++i) {
        f >> x;
        update(i, x);
    }
    while (M--) {
        f >> tip >> x;
        if (tip == 0) {
            f >> y;
            update(x, y);
        } else if (tip == 1) {
            f >> y;
            g << query(y) -  query(x - 1) << '\n';
        } else {
            int pos = 0, X = x;
            for (int step = (1 << 30); step; step >>= 1) {
                if (pos + step <= N && aib[pos + step] < x) {
                    pos += step;
                    x -= aib[pos];
                }
            }

            ++pos;
            if (query(pos) != X) {
                g << -1 << '\n';
            } else {
                g << pos << '\n';
            }
        }
    }
    return 0;
}