Pagini recente » Borderou de evaluare (job #1248854) | Borderou de evaluare (job #928384) | Cod sursa (job #2686243) | Borderou de evaluare (job #2376906) | Cod sursa (job #2722320)
#include <fstream>
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
#define NMAX 100005
#define zeros(x) ((x^(x-1))&x)
int AIB[NMAX],N,M;
void Add(int x,int val)
{
for(int i=x; i<=N; i+=zeros(i))
AIB[i]+=val;
}
int Get(int x)
{
int res=0;
for(int i=x; i>0; i-=zeros(i))
res+=AIB[i];
return res;
}
int Search(int x)
{
int st=1,dr=N,mid,val,sol=-1;
while(st<=dr)
{
mid=(st+dr)/2;
val=Get(mid);
if(val==x)
{
sol=mid;
dr=mid-1;
}
else if(val<x)
st=mid+1;
else dr=mid-1;
}
return sol;
}
int main()
{
int i,op,a,b,x;
cin>>N>>M;
for(i=1; i<=N; i++)
{
cin>>x;
Add(i,x);
}
for(i=1; i<=M; i++)
{
cin>>op;
if(op==0)
{
cin>>a>>b;
Add(a,b);
}
else if(op==1)
{
cin>>a>>b;
cout<<Get(b)-Get(a-1)<<'\n';
}
else
{
cin>>a;
cout<<Search(a)<<'\n';
}
}
return 0;
}