Cod sursa(job #711080)
#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
#define dim 100005
int n, m, v[dim];
inline int lsb(int x)
{
return x&-x;
};
void update(int poz, int val)
{
for ( ; poz<=n ; poz+= lsb(poz) )
v[poz]+=val;
}
void read()
{
int i, x;
fin>>n >>m;
for(i=1;i<=n;++i)
{
fin>>x;
update(i,x);
}
}
int query(int poz)
{
int sum=0;
for(;poz;poz-=lsb(poz))
sum+=v[poz];
return sum;
}
int search(int val)
{
int i, step=1;
for(i=1;step<n;step<<=1);
for(i=0;step;step>>=1)
if(val>=v[i+step])
{
i+=step;
val-=v[i];
if(val==0)
return i;
}
return -1;
}
void solve()
{
int i, tip, x, y;
for(i=1;i<=m;++i)
{
fin>>tip;
if(tip==0)
{
fin>>x >>y;
update(x,y);
}
else
if(tip==1)
{
fin>>x >>y;
fout<<query(y)-query(x-1) <<'\n';
}
else
{
fin>>x;
fout<<search(x)<<'\n';
}
}
}
int main()
{
read();
solve();
return 0;
}