Pagini recente » Cod sursa (job #679451) | Cod sursa (job #2739470)
#include <iostream>
#include <fstream>
using namespace std;
ifstream be("aib.in");
ofstream ki("aib.out");
int getSum(int bitr[],int idx)
{
int s=0;
while(idx>0)
{
s+=bitr[idx];
idx-=idx&(-idx);
}
return s;
}
void update(int bitr[],int x,int val,int n)
{
int idx=x+1;
while(idx<=n)
{
bitr[idx]+=val;
idx=idx+(idx&(-idx));
}
}
int sch(int bitr[],int x,int n)
{
int j;
for(j=1;j<n;j<<=1);
for(int i=0;i<j;j>>=1)
{
if(i+j<=n)
{
if(x>=bitr[i+j])
{
i+=j;
x-=bitr[i];
if(!x)return i;
}
}
}
return -1;
}
int main()
{
int n,m;
be>>n>>m;
int bitr[n+1]={0};
for(int i=0;i<n;i++)
{
int x;
be>>x;
update(bitr,i,x,n);
}
for(int i=0;i<m;i++)
{
int j;
be>>j;
if(j!=2)
{
int x,y;
be>>x>>y;
if(j==0)
update(bitr,x-1,y,n);
else ki<<(getSum(bitr,y)-getSum(bitr,x-1))<<endl;
}
else {
int x;
be>>x;
ki<<sch(bitr,x,n)<<endl;
}
}
return 0;
}