Cod sursa(job #740038)
#include <fstream>
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
const int N=100006;
int aib[N],n;
int step(int x)
{
return x&(-x);
}
int query(int x)
{
int sum=0;
for(;x;x-=step(x))
sum+=aib[x];
return sum;
}
void update(int x,int val)
{
for(;x<=n;x+=step(x))
aib[x]+=val;
}
int bs(int val)
{
int i,pas=1<<16;
for(i=0;pas;pas>>=1)
if(i+pas<=n && aib[i+pas]<=val)
{
i+=pas;
val-=aib[i];
}
if(val)
return -1;
return i;
}
int main()
{
int m,q,x,y;
in>>n>>m;
for(int i=1;i<=n;i++)
{
in>>x;
update(i,x);
}
while(m--)
{
in>>q;
if(q==1)
{
in>>x>>y;
out<<query(y)-query(x-1)<<"\n";
continue;
}
if(q==0)
{
in>>x>>y;
update(x,y);
continue;
}
in>>x;
out<<bs(x)<<"\n";
}
return 0;
}