Pagini recente » Borderou de evaluare (job #2924566) | Cod sursa (job #676328) | Cod sursa (job #785051)
Cod sursa(job #785051)
#include<iostream>
#include<fstream>
using namespace std;
const int maxx=100005;
int n,m,i,j,x,aib[maxx],tip,a,b,sum,poz;
int pas(int poz)
{
return poz & -poz;
}
void update(int i,int val)
{
while(i<=n)
{
aib[i]+=val;
i+=pas(i);
}
}
int suma(int poz)
{
int s=0;
while(poz)
{
s+=aib[poz];
poz-=pas(poz);
}
return s;
}
int search(int left,int right)
{
int mij,s1;
while(left<right)
{
mij=(left+right)/2;
s1=suma(mij);
if(s1>=a)
right=mij;
else
left=mij+1;
}
if(suma(right)==a)
return right;
return -1;
}
int main()
{
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
update(i,x);
}
for(j=1;j<=m;j++)
{
scanf("%d ",&tip);
if(tip==0)
{
scanf("%d %d\n",&a,&b);
update(a,b);
}
else
if(tip==1)
{
scanf("%d %d\n",&a,&b);
sum=suma(b)-suma(a-1);
printf("%d\n",sum);
}
else
{
scanf("%d\n",&a);
poz=search(1,n);
printf("%d\n",poz);
}
}
return 0;
}