Pagini recente » Cod sursa (job #2229369) | Cod sursa (job #816236) | Cod sursa (job #2839399) | Cod sursa (job #132605) | Cod sursa (job #1150162)
#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int N, M, x, tip, val, aib[100002], poz, a, b;
int lsb(int x) { return -x&x; }
void update(int poz, int val)
{
while (poz<=N)
aib[poz]+=val, poz+=lsb(poz);
}
int query(int poz)
{
int res=0;
while (poz)
res+=aib[poz], poz-=lsb(poz);
return res;
}
int main()
{
f>>N>>M;
for (int i=1; i<=N; ++i)
f>>x, update(i, x);
for (int i=1; i<=M; ++i)
{
f>>tip;
if (!tip) f>>poz>>val, update(poz, val);
else if (tip==1) f>>a>>b, g<<query(b)-query(a-1)<<'\n';
else
{
int ans=0, sum, aux; f>>sum; aux=sum;
for (int i=(1<<16); i>0; i>>=1)
if (i+ans<=N && aib[i+ans]<=sum)
sum-=aib[i+ans], ans+=i; //++ans;
if (query(ans)!=aux) g<<-1<<'\n';
else g<<ans<<'\n';
}
}
return 0;
}