HackerEarth Incremental queries problem solution

In this HackerEarth Incremental queries problem solution You are given an array A consisting of N elements A1,A2,A3,...,AN. You must process N queries and there are two types of queries:

1. L R: Replace Lth element by R, that is, AL = R.
2. L R: You are required to print the minimum number of operations to make all elements equal in subarrays AL, AL+1, ..., AR.

You can perform the following operation in order to make elements equal:

Select any index L and replace AL with AL + 1 or AL + 2.

HackerEarth Incremental queries problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "\n"
#define test ll txtc; cin>>txtc; while(txtc--)
typedef long long int ll;
typedef long double ld;
ll a[200001];
struct obj{
    ll sum,odd,even,maxm;
};
obj ans;
obj seg_tree[4*200001];
void build(int index,int l,int r){
    if(l==r){
        seg_tree[index].sum=a[l];
        seg_tree[index].odd=(a[l]%2);
        seg_tree[index].even=(a[l]%2==0?1:0);
        seg_tree[index].maxm=a[l];
        return ;
    }
    ll mid=(l+r)/2;
    build(2*index+1,l,mid);
    build(2*index+2,mid+1,r);
    seg_tree[index].sum=seg_tree[2*index+1].sum+seg_tree[2*index+2].sum;
    seg_tree[index].odd=seg_tree[2*index+1].odd+seg_tree[2*index+2].odd;
    seg_tree[index].even=seg_tree[2*index+1].even+seg_tree[2*index+2].even;
    seg_tree[index].maxm=max({seg_tree[2*index+1].maxm,seg_tree[2*index+2].maxm});
}
void update(int index,int l,int r,int node,ll val){
    if(l==r){
       seg_tree[index].sum=val;
        seg_tree[index].odd=(val%2);
        seg_tree[index].even=(val%2==0?1:0);
        seg_tree[index].maxm=val;
       return ; 
    }
    int mid=(l+r)/2;
    if(node>=l && node<=mid) update(2*index+1,l,mid,node,val);
    else update(2*index+2,mid+1,r,node,val);
    seg_tree[index].sum=seg_tree[2*index+1].sum+seg_tree[2*index+2].sum;
    seg_tree[index].odd=seg_tree[2*index+1].odd+seg_tree[2*index+2].odd;
    seg_tree[index].even=seg_tree[2*index+1].even+seg_tree[2*index+2].even;
    seg_tree[index].maxm=max({seg_tree[2*index+1].maxm,seg_tree[2*index+2].maxm});
}
void query(int index,int low,int high,int l,int r){
    //cout<<index<<" "<<low<<" "<<high<<" "<<l<<" "<<r<<endl;
    if(low>=l && high<=r){
        ans.sum+=seg_tree[index].sum;
        ans.odd+=seg_tree[index].odd;
        ans.even+=seg_tree[index].even;
        ans.maxm=max(ans.maxm,seg_tree[index].maxm);
        return;
    }
    if(low>r || high<l){
        return;
    }
    ll mid=(low+high)/2;
    query(2*index+1,low,mid,l,r);
    query(2*index+2,mid+1,high,l,r);
}
ll solve(ll l, ll r,ll n){
    l--; r--;
    ans.sum=0; ans.odd=0; ans.even=0; ans.maxm=0;
    query(0,0,n-1,l,r);
    //cout<<"sum="<<ans.sum<<" odd="<<ans.odd<<" even="<<ans.odd<<" maxm="<<ans.maxm<<endl;
    ll res=0,to_sum;
    to_sum=ans.maxm*(r-l+1);
    to_sum-=ans.sum;
    if(ans.maxm%2==1){
        res+=ans.even;
        to_sum-=ans.even;
    }
    else{
        res+=ans.odd;
        to_sum-=ans.odd;
    }
    res+=(to_sum/2);
    return res;
}
int main() {
    FIO;
    ll n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    build(0,0,n-1);
    while(m--){
        ll type,l,r;
        cin>>type>>l>>r;
        if(type==1){
            l--;
            update(0,0,n-1,l,r);
            a[l]=r;
        }
        else{
            cout<<solve(l,r,n)<<endl;
        }
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 14;
struct Node{
    int mx, cnt[2];
    ll sum;
    Node(){
        mx = sum = cnt[0] = cnt[1] = 0;
    }
    Node(int x){
        sum = mx = x;
        cnt[x % 2] = 1;
        cnt[!(x % 2)] = 0;
    }
    ll ans(){
        return (mx * ll(cnt[0] + cnt[1]) - sum) / 2 + (cnt[!(mx % 2)] + 1) / 2;
    }
    Node operator +(Node o) const{
        o.mx = max(o.mx, mx);
        o.sum = o.sum + sum;
        o.cnt[0] += cnt[0];
        o.cnt[1] += cnt[1];
        return o;
    }
}  seg[maxn * 2];
int n, q;
void upd(int p, int x){
    for(seg[p += n] = x; p >>= 1; )
        seg[p] = seg[p * 2] + seg[p * 2 + 1];
}
Node get(int l, int r){
    Node ans;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1){
        if(l % 2)
            ans = seg[l++] + ans;
        if(r % 2)
            ans = ans + seg[--r];
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for (int i = n; i < 2 * n; i++){
        int x;
        cin >> x;
        seg[i] = x;
    }
    for(int i = n - 1; i > 0; i--)
        seg[i] = seg[i * 2] + seg[i * 2 + 1];
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        l--;
        if(t == 1)
            upd(l, r);
        else
            cout << get(l, r).ans() << '\n';
    }
}