Pagini recente » Cod sursa (job #2526465) | Cod sursa (job #2060207) | Cod sursa (job #864401) | Cod sursa (job #144113) | Cod sursa (job #3176582)
#include <stdio.h>
#include <iostream>
#define N_MAX 100001
#define N_LOG 20
using namespace std;
int n, m;
int aib[N_MAX];
int leastSignificantBit (int x){
return x & -x;
}
// void build (){
// for (int i=1; i<=n; ++i){
// aib[i] += arr[i];
// if (i + leastSignificantBit(i) <= n)
// aib[i + leastSignificantBit(i)] += aib[i];
// }
// }
void update (int idx, int value){
// arr[idx] = value;
while (idx <= n){
aib[idx] += value;
idx += leastSignificantBit(idx);
}
}
int query (int Idx){
long long Sum = 0;
while (Idx){
Sum += aib[Idx];
Idx -= leastSignificantBit(Idx);
}
return Sum;
}
int binaryLifting (long long value){
int mask, pos, sum;
pos = 0;
sum = 0;
for (int mask=24; mask>=0; mask--){
if (pos + (1<<mask) <= n && sum + aib[pos+(1<<mask)] <= value){
sum += aib[pos+(1<<mask)];
pos += (1<<mask);
}
}
if (sum == value)
return pos;
return -1;
}
int main (){
FILE *in, *out;
in = fopen ("aib.in", "r");
out = fopen ("aib.out", "w");
fscanf(in, "%d%d", &n, &m);
int num;
for (int i=1; i<=n; ++i){
fscanf (in, "%d", &num);
update(i, num);
}
int op, x, y;
for (int i=1; i<=m; ++i){
fscanf(in, "%d", &op);
if (op == 0){
fscanf(in, "%d%d", &x, &y);
update(x, y);
}
else if (op == 1){
fscanf(in, "%d%d", &x, &y);
fprintf (out, "%d \n", query(y) - query(x-1));
}
else{
fscanf(in, "%d", &x);
fprintf(out, "%d \n", binaryLifting(x));
}
}
return 0;
}