Pagini recente » Cod sursa (job #2813868) | Cod sursa (job #1217643) | Cod sursa (job #811856) | Cod sursa (job #61785) | Cod sursa (job #993966)
Cod sursa(job #993966)
#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n, aib[100005], m;
inline int zero(int &x) { return x & -x;}
inline void update(int poz, int value)
{
while (poz<=n) aib[poz]+=value, poz+=zero(poz);
}
inline int query(int poz)
{
int ans=0;
while (poz) ans+=aib[poz], poz-=zero(poz);
return ans;
}
int main()
{
int x; f>>n>>m;
for (int i=1; i<=n; i++) f>>x, update(i, x);
for (int i=1; i<=m; i++)
{
int tip; f>>tip;
if (tip==0)
{
int pos, val; f>>pos>>val;
update(pos, val);
}
else if (tip==1)
{
int left, right; f>>left>>right;
g<<query(right)-query(left-1)<<'\n';
}
else
{
int x, q, ans=0; f>>x; q=x;
for (int i=1<<16; i>0; i>>=1)
if (i+ans<=n && aib[ans+i]<x) x-=aib[ans+i], ans+=i;
++ans;
if (ans!=-1 && query(ans)!=q) ans=-1;
g<<ans<<'\n';
}
}
return 0;
}