Cod sursa(job #601662)
#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
#define maxn 100005
int N,M,i,x,K,a,b;
int Arb[maxn];
inline int min(int a, int b)
{
return a<b ? a : b;
}
void update(int poz, int val)
{
while(poz<=N)
{
Arb[poz]+=val;
poz+=(poz & (-poz));
}
}
int suma(int poz)
{
int P=0,S=0;
while(poz)
{
S+=Arb[poz];
poz-=(poz & (-poz));
}
return S;
}
int cbin(int val)
{
int st,dr,m,S,Min;
st=1; dr=N; m=(st+dr)/2;
Min=maxn;
while(st<=dr)
{
S=suma(m);
if(S>=val)
if(S==val) Min=min(Min,m), st=dr+1;
else dr=m-1;
else
st=m+1;
m=(st+dr)/2;
}
if(Min==maxn) return -1;
return Min;
}
int main()
{
fin >> N >> M;
for(i=1;i<=N;i++)
{
fin >> x;
update(i,x);
}
for(;M;M--)
{
fin >> K;
if(K<2)
{
fin >> a >> b;
if(K==0) update(a,b);
else fout << suma(b)-suma(a-1) << '\n';
}
else
{
fin >> a;
b = cbin(a);
fout << b << '\n';
}
}
}