Cod sursa(job #345917)
// 5.09.2009
#include<stdio.h>
int a[100010];
int BIT[100010];
int N;
int dif;
int cc;
int tc;
int P;
int poz;
int Q;
void Update(int P)
{
while (P <= N)
{
BIT[P] += dif;
P += (P & -P);
}
}
int Query(int L)
{
int sum = 0;
while (L > 0)
{
sum += BIT[L];
L -= (L & -L);
}
return sum;
}
int BinSrch(int V)
{
int st = 1;
int dr = N;
poz = -1;
while (st <= dr)
{
int C = Query((st + dr) / 2);
if (C > V) dr = (st + dr) / 2 - 1;
else
if (C < V) st = (st + dr) / 2 + 1;
else
{
poz = (st + dr) / 2;
break;
}
}
if (poz != -1)
{
//while (a[poz] == 0) poz--;
}
return poz;
}
int main()
{
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
scanf("%d %d",&N,&tc);
for(int i = 1; i <= N; i++)
scanf("%d",&a[i]);
for(int i = 1; i <= N; i++)
{
dif = a[i];
Update(i);
}
for(int i = 1; i <= tc; i++)
{
scanf("%d",&cc);
if (cc == 0)
{
scanf("%d %d",&P,&dif);
a[P] = Q;
Update(P);
}
else
if (cc == 1)
{
scanf("%d %d",&P,&Q);
int S1 = Query(Q);
int S2 = Query(P-1);
printf("%d\n",S1-S2);
}
else
if (cc == 2)
{
scanf("%d",&P);
printf("%d\n",BinSrch(P));
}
}
}