In this HackerEarth Queries problem solution, you are given an array A of N integers. Now, you are required to process queries of the following two types.
  1. pos val: Multiply val to A[pos] i.e A[pos] = A[pos] * val.  
  2. Print an integer X such that the absolute difference between the following two values (A[1] * A[2] * ...... * A[X]) and (A[X+1] * A[X+2] * ........ * A[N]) is minimized. If there are multiple such values of X, then print the smallest one.

HackerEarth Queries problem solution


HackerEarth Queries problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll M=1e9+7;
const ld eps=1e-10;
ld inf=1e25;
ll n,m;
ll N=100002;
ld bit[100005],a[100005];

void update(ll idx, ld val){
    ll x=idx;
    for(;x<=n;x+=(x&-x))
        bit[x]+=val;
}

ld query(ll idx){
    ld ans=0;
    ll x=idx;
    for(;x>0;x-=(x&-x))
        ans+=bit[x];
    return ans;
}

ll low(ll l, ll h, ld sum)
{
    ll ret=1;
    while(l<=h)
    {
        ll mid=(l+h)>>1;
        ld val=query(mid);
        if(val-sum>-eps)
            h=mid-1;
        else
        {
            ret=mid;
            l=mid+1;
        }
    }
    return ret;
}

ll up(ll l, ll h, ld sum)
{
    ll ret=n;
    while(l<=h)
    {
        ll mid=(l+h)>>1;
        ld val=query(mid);
        if(val-sum>eps)
        {
            ret=mid;
            h=mid-1;
        }
        else
            l=mid+1;
    }
    return ret;
}

ll bin(ll l, ll h, ld sum)
{
    ll ret=-1;
    while(l<=h)
    {
        ll mid=(l+h)>>1;
        ld val=query(mid);
        if(fabsl(val-sum)<eps)
        {
            ret=mid;
            h=mid-1;
        }
        else if(val-sum>eps)
            h=mid-1;
        else
            l=mid+1;
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>n>>m;
    ld tot=0.0;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        ld val=log2(a[i]);
        a[i]=val;
        tot+=val;
        update(i,val);
    }
    while(m--)
    {
        ll type;
        cin>>type;
        if(type==1)
        {
            ll i;
            ld x;
            cin>>i>>x;
            ld val=log2(x);
            update(i,val);
            tot+=val;
            a[i]+=val;
        }
        else
        {
            ld sum=tot/((ld)(2.0));
            ll pos=bin(1,n,sum);
            if(pos==-1)
                pos=low(1,n,sum);
            pos=bin(1,n,query(pos));

            ld val1=query(pos);
            ld val2=tot-val1;
            ld ans=pos;
            ld mini=fabsl(val1-val2);

            for(ll j=pos-3;j<=pos+3;j++)
            {
                if(j>0 && j<n)
                {
                    val1=query(j);
                    val2=tot-val1;
                    if(fabsl(val1-val2)-mini<-eps)
                    {
                        mini=fabsl(val1-val2);
                        ans=j;
                    }
                }
            }

            pos=-1;
            pos=bin(1,n,sum-0.1);
            if(pos==-1)
                pos=low(1,n,sum-0.1);

            pos=bin(1,n,query(pos));

            for(ll j=pos-3;j<=pos+3;j++)
            {
                if(j>0 && j<n)
                {
                    val1=query(j);
                    val2=tot-val1;
                    if(fabsl(val1-val2)-mini<-eps)
                    {
                        mini=fabsl(val1-val2);
                        ans=j;
                    }
                }
            }

            pos=up(1,n,sum);
            val1=query(pos);
            val2=tot-val1;

            for(ll j=pos-3;j<=pos+3;j++)
            {
                if(j>0 && j<n)
                {
                    val1=query(j);
                    val2=tot-val1;
                    if(fabsl(val1-val2)-mini<-eps)
                    {
                        mini=fabsl(val1-val2);
                        ans=j;
                    }
                }
            }
            cout<<ans<<"\n";
        }
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1e5 + 17;
ld fen[maxn], a[maxn];
void upd(int p, ld x){
    for(p++; p < maxn; p += p & -p)
        fen[p] += x;
}
ld get(int p){
    ld ans = 0;
    for(; p; p ^= p & -p)
        ans += fen[p];
    return ans;
}
int n, m;
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    ld s = 0;
    for(int i = 0; i < n; i++){
        ll x;
        cin >> x;
        upd(i, log(x));
        s += log(x);
    }
    while(m--){
        int t;
        cin >> t;
        if(t == 1){
            int i;
            ll x;
            cin >> i >> x;
            i--;
            upd(i, log(x));
            s += log(x);
        }
        else{
            int lo = -1, hi = n;
            auto f = [&s](int i){
                return abs(get(i + 1) - (s - get(i + 1)));
            };
            while(hi - lo > 2){
                int lh = lo + (hi - lo) / 3, rh = hi - (hi - lo) / 3;
                if(f(rh) >= f(lh))
                    hi = rh;
                else
                    lo = lh;
            }
            cout << lo + 2 << '\n';
        }
    }
}