Pagini recente » Cod sursa (job #560744) | Cod sursa (job #1543168) | Cod sursa (job #2103171) | Cod sursa (job #1776745) | Cod sursa (job #2019629)
#include <fstream>
#define ub(x) (x&(-x))
using namespace std;
int x,i,y,z,n,m,aib[1000003],st,dr,j,pozitie,k;
ifstream f("aib.in");
ofstream g("aib.out");
int suma(int pozitie)
{
int s=0;
for(j=pozitie;j>0;j-=ub(j))
{
s+=aib[j];
}
return s;
}
void update(int pozitie,int val)
{
for(j=pozitie;j<=n;j+=ub(j))
aib[j]+=val;
}
int main()
{
f>>n>>m;
for(i=1;i<=n;i++)
{
f>>x;
update(i,x);
}
for(i=1;i<=m;i++)
{
f>>x;
if(x==0)
{
f>>y>>z;
update(y,z);
}
else if(x==1)
{
f>>y>>z;
g<<suma(z)-suma(y-1)<<'\n';
}
else if(x==2)
{
f>>y;
st=1;
dr=n;
pozitie=-1;
while(st<=dr && pozitie==-1)
{
k=(st+dr)/2;
if(suma(k)==y)pozitie=k;
else if(suma(k)>y)dr=k-1;
else st=k+1;
}
g<<pozitie<<'\n';
}
}
return 0;
}