HackerEarth Bob And Array Queries problem solution

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;
}

int add(ll a,ll b)
{
    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);
            
            res=add(res,mul(1ll<<j,add(zz1,zz2)));
        }
        
        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 yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#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++;
    }
}