Pagini recente » Cod sursa (job #564086) | Cod sursa (job #788026) | Cod sursa (job #3032160) | Cod sursa (job #2745113) | Cod sursa (job #3267172)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("aib.in") ;
ofstream fout ("aib.out") ;
int n , i , x , y , ind , nr , m , a[100001] , v[100001] , caz , av , b , j ;
void add ( int ind , int x )
{
for ( int i = ind ; i <= n ; i += ( i & ( - i ) ) )
a[i] += x ;
}
int sum ( int x )
{
int s = 0 ;
for ( int i = x ; i >= 1 ; i -= ( i & ( - i ) ) )
s += a[i] ;
return s ;
}
int main()
{
fin >> n >> m ;
for ( i = 1 ; i <= n ; i ++ )
{
fin >> v[i] ;
add ( i , v[i] ) ;
}
for ( j = 1 ; j <= m ; j ++ )
{
fin >> caz ;
if ( caz == 0 )
{
fin >> ind >> nr ;
add ( ind , nr ) ;
}
else if ( caz == 1 )
{
fin >> av >> b ;
fout << sum ( b ) - sum ( av - 1 ) << '\n' ;
}
else
{
fin >> x ;
int st = 1 , dr = n , mij , poz = 0 ;
while ( st <= dr && poz == 0 )
{
mij = ( st + dr ) / 2 ;
y = sum(mij) ;
if ( y == x )
poz = mij ;
else if ( y > x )
st = mij + 1 ;
else dr = mij - 1 ;
}
if ( poz == 0 )
fout << -1 << '\n' ;
else
fout << poz ;
}
}
return 0;
}