In this HackerEarth Bob And Array Queries problem solution Bob has an array A[] of N integers. Initially, all the elements of the array are zero. Bob asks you to perform Q operations on this array.

There are three types of operations that can be performed:
1. X: Update the value of A[X] to  2 * A[X] + 1.
2. X: Update the value A[X] to [A[x]/2]
3. X Y: Take all the A[i] such that  X <= i <= Y and convert them into their corresponding binary strings. Now concatenate all the binary strings and find the total no. of '1' in the resulting string.

## HackerEarth Bob And Array Queries problem solution.

```#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;

#define pb push_back

const int maxn=(int)(2e5+5),LN=41;
const ll mod=(ll)(1e9+7);
ld pi=2.0*acos(0.0);
ll a[maxn];
int pre[LN][maxn];

int mul(ll a,ll b)
{
a%=mod;b%=mod;

ll ret=(a*b);

if(ret>=mod)
{
ret%=mod;
}

return (int)ret;
}

{
a%=mod;b%=mod;

ll ret=a+b;

if(ret>=mod)
{
ret%=mod;
}

return (int)ret;
}

int sub(ll a,ll b)
{
a%=mod;b%=mod;

ll ret=a-b;

if(ret<0)
{
ret+=mod;
}

return (int)ret;
}

static int poww(ll a,ll b)
{
ll x=1,y=a;

while(b>0)
{
if(b%2)
{
x=mul(x,y);
}

y=mul(y,y);b/=2;
}

return (int)(x%mod);
}

const int inv_6=poww(6,mod-2),inv_2=poww(2,mod-2);

int nC3(ll n)
{
if(n<3)
{
return 0;
}

return mul(mul(n,mul(n-1,n-2)),inv_6);
}

int nC2(ll n)
{
if(n<2)
{
return 0;
}

return mul(n,mul(n-1,inv_2));
}

int main()
{
int n;scanf("%d",&n);

assert(n>=1 && n<=(int)(1e5));

for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);

assert(a[i]>=1 && a[i]<=(ll)(1e12));
}

for(int j=0;j<LN;j++)
{
int now=0;ll zz=(1ll<<j);

for(int i=1;i<=n;i++)
{
if((zz&a[i])!=0)
{
now++;
}

pre[j][i]=now;
}
}

int q,two;scanf("%d%d",&q,&two);

assert (q>=1 && q<=(int)(5e5) && two==2);

for(int i=0;i<q;i++)
{
int l,r;scanf("%d%d",&l,&r);

assert (l>=1 && l<=r && r<=n);

int res=0,size=(r-l+1);

for(int j=0;j<LN;j++)
{
int val1=(pre[j][r]-pre[j][l-1]),val0=size-val1;

int zz1=mul(val1,nC2(val0)),zz2=nC3(val1);

}

printf("%d\n",res);
}

return 0;
}```

### Second solution

```#include <bits/stdc++.h>
using namespace std;

#include<limits>
#define ll long long

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd

#define debugdec int deb=1;
#define debug() cout<<"real_flash>> "<<(deb++)
#define pb push_back
#define mk make_pair
#define MEM(a,b) memset(a,(b),sizeof(a))
#define TEST int test; cin >> test;while(test--)
#define si(x) scanf("%d",&x)
#define author real_flash
#define rep(p,q,r) for(int p=q;p<r;p++)
#define repr(p,q,r) for(int p=q;p>=r;p--)
#define repit(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define si2(x,y) scanf("%d %d",&x,&y)
#define si3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define FIND(x,y) x.find(y)==x.end()
#define sl(x) scanf("%lld",&x)
#define prl(x) printf("%lld\n",x)
#define ff first
#define ss second
#define BE(a) a.begin(), a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define INF 111111111111111LL
#define mo 1000000007
#define PI 3.141592653589793

typedef pair<int, int > pii;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<ll, ll> pll;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a;}
int MAX=numeric_limits<int>::max();
const int N=1e6+5;

int BIT[N], a[N];

inline void update(int x, int val)
{
for(; x <N; x += x&-x)
BIT[x] += val;
}
inline int query(int x)
{
int sum = 0;
for(; x > 0; x -= x&-x)
sum += BIT[x];
return sum;
}

int n,q,ch,x,y;
int cnt[N],cnt3=0;;
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
si2(n,q);
assert(n>=1&&n<=500000);
assert(q>=1&&q<=500000);
int ma=0;
int hh=1;
while(q--)
{
si(ch);
assert(ch>=1&&ch<=3);

if(ch==1)
{
si(x);
if(x<1||x>n)
{cout<<"this x= "<<x<<" "<<hh<<"\n";
break;
}
cnt[x]++;
ma=max(ma,cnt[x]);
update(x,1);
}
else if(ch==2)
{
si(x);
y=query(x);
if(x>1)
y-=query(x-1);
if(y>=1)
update(x,-1);
}
else
{
cnt3++;
si2(x,y);
assert(x>=1&&x<=n);
assert(y>=1&&y<=n);
printf("%d\n",query(y)-query(x-1));
}
hh++;
}
}```