Pagini recente » Cod sursa (job #883376) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #1738226) | Cod sursa (job #1100580)
#include<fstream>
using namespace std;
int aib[100005],i,j,n,m,op,a,b;
void update(int poz, int val) {
while (poz<=n) { aib[poz]+=val; poz+=(poz&(-poz)); }
}
int suma(int poz) {
int rez=0;
while (poz>=1) { rez+=aib[poz]; poz-=(poz&(-poz)); }
return(rez);
}
int main(void) {
ifstream fin("aib.in");
ofstream fout("aib.out");
fin>>n>>m;
for (i=1; i<=n; ++i) {
fin>>a;
update(i,a);
}
for (i=1; i<=m; ++i) {
fin>>op;
if (op==0) {
fin>>a>>b;
update(a,b);
}
else if (op==1){
fin>>a>>b;
fout<<suma(b)-suma(a-1)<<"\n";
}
else {
fin>>a;
int l=1, r=n, mid;
bool ok=0;
while (l<=r) {
mid=(l+r)/2;
int s=suma(mid);
if (s==a) { ok=1; break; }
else if (s>a) r=mid-1;
else l=mid+1;
}
if (ok) fout<<mid<<"\n"; else fout<<"-1\n";
}
}
return(0);
}