Pagini recente » Cod sursa (job #866795) | Cod sursa (job #2430380) | Cod sursa (job #2197920) | Cod sursa (job #867702) | Cod sursa (job #1757389)
#include <cstdio>
#define NMAX 100001
#define putereZerouri(x) ((x ^ (x - 1)) & x)
int aib[NMAX];
int aflaPozitie(int suma, int n);
int aflaSuma(int poz);
void modifica(int poz, int val, int n);
int main()
{
FILE *fin = fopen("aib.in", "r");
FILE *fout = fopen("aib.out", "w");
int n, m;
fscanf(fin, "%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
int x;
fscanf(fin, "%d", &x);
modifica(i, x, n);
}
while (m--) {
int r, x;
fscanf(fin, "%d%d", &r, &x);
if (r == 2) {
fprintf(fout, "%d\n", aflaPozitie(x, n));
}
else {
int y;
fscanf(fin, "%d", &y);
if (r == 0)
modifica(x, y, n);
else fprintf(fout, "%d\n", aflaSuma(y) - aflaSuma(x - 1));
}
}
return 0;
}
int aflaPozitie(int suma, int n)
{
int putere = 1;
while (putere < n)
putere <<= 1;
int poz = 0;
while (putere > 0) {
if (poz + putere <= n && aflaSuma(poz + putere) <= suma)
poz += putere;
putere >>= 1;
}
return (aflaSuma(poz) == suma) ? poz : -1;
}
int aflaSuma(int poz)
{
int suma = 0;
while (poz != 0) {
suma += aib[poz];
poz -= putereZerouri(poz);
}
return suma;
}
void modifica(int poz, int val, int n)
{
while (poz <= n) {
aib[poz] += val;
poz += putereZerouri(poz);
}
}