Pagini recente » Rezultatele filtrării | Cod sursa (job #1421161) | Cod sursa (job #419391) | Cod sursa (job #769243) | Cod sursa (job #2883588)
#include<bits/stdc++.h>
using namespace std;
int aib[100005];
int n, m;
void q1(int a, int b);
int lsb(int i)
{
return (~i + 1) & i;
}
void citire()
{
freopen("aib.in", "r", stdin);
freopen("aib.out", "w", stdout);
scanf("%d%d", &n, &m);
for ( int i = 1 ; i <= n ; i++ )
{
int aux;
scanf("%d", &aux);
q1(i, aux);
}
}
void afisare()
{
for ( int i = 1 ; i <= n ; i++ )
{
cout<<aib[i]<<" ";
}
}
void q1(int a, int b)
{
int i = a;
while ( i <= n )
{
aib[i] += b;
i += lsb(i);
}
}
int sumPref(int x) ///suma [1, x]
{
int ans = 0;
int i = x;
while ( i >= 1 )
{
ans += aib[i];
i -= lsb(i);
}
return ans;
}
void q2(int a, int b)
{
cout<<sumPref(b) - sumPref(a-1)<<'\n';
}
void q3(int a)
{
int st, dr;
st = 1;
dr = n;
int ans = INT_MAX;
while ( st <= dr )
{
int mij = ( st + dr ) / 2;
int aux = sumPref(mij);
if ( aux == a )
{
cout<<mij<<'\n';
return;
}
else if ( aux > a )
{
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
cout<<-1<<'\n';
}
void rez()
{
for ( int i = 1 ; i <= m ; i++ )
{
int c;
scanf("%d", &c);
if ( c == 0 )
{
int a, b;
scanf("%d%d", &a, &b);
q1(a,b);
}
else if ( c == 1 )
{
int a, b;
scanf("%d%d", &a, &b);
q2(a,b);
}
else
{
int a;
scanf("%d", &a);
q3(a);
}
}
}
int main()
{
citire();
rez();
return 0;
}