Cod sursa(job #283668)

Utilizator victorsbVictor Rusu victorsb Data 19 martie 2009 15:08:34
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <cstdio>

using namespace std;

#define FIN "aib.in"
#define FOUT "aib.out"
#define MAX_N 100015

int N, M;
int A[MAX_N];
int aib[MAX_N];

void read() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i)
        scanf("%d", &A[i]);
}

void update(int pos, int val) {
    while (pos <= N) {
        aib[pos] += val;
        pos += (pos ^ (pos - 1)) & pos;
    }
}

int query1(int pos) {
    int ret = 0;
    
    while (pos > 0) {
        ret += aib[pos];
        pos -= (pos ^ (pos - 1)) & pos;
    }

    return ret;
}

int query2(int val) {
    int step, pos, tmp = val;
    for (step = 1; (step << 1) <= N; step <<= 1);
    for (pos = 0; step; step >>= 1)
        if (pos + step <= N && aib[pos + step] < tmp) {
            pos += step;
            tmp -= aib[pos];
        }
    ++pos;
    if (1 <= pos && pos <= N && query1(pos) == val)
        return pos;
    else
        return -1;
}

void solve() {
    for (int i = 1; i <= N; ++i)
        update(i, A[i]);
    
    for (int i = 1; i <= M; ++i) {
        int tip, a, b;
        scanf("%d", &tip);
        if (tip == 0) {
            scanf("%d %d", &a, &b);
            update(a, b);
            A[a] += b;
        }
        else if (tip == 1) {
            scanf("%d %d", &a, &b);
            printf("%d\n", query1(b) - query1(a - 1));
        }
        else {
            scanf("%d", &a);
            printf("%d\n", query2(a));
        }
    }
}

int main() {
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    read();
    solve();
    return 0;
}