# HackerEarth Range of a query problem solution

In this HackerEarth Range of a query problem solution, you are given an array A of N integers. you are required to answer Q queries.

## HackerEarth Range of a query problem solution.

`#include<bits/stdc++.h>#define int long long intusing namespace std;struct nod{    bool is_full;    int lval;    int lcnt;    int rval;    int rcnt;    int mx;};nod merge(nod a,nod b){    nod ret;    if(a.is_full && b.is_full && a.lval == b.lval ){        ret.is_full=true;        ret.lval = a.lval;        ret.rval = a.lval;        ret.lcnt = a.lcnt + b.lcnt;        ret.rcnt = ret.lcnt;        //ret.mx = a.mx + b.mx;        if(ret.rval< ret.rcnt){            ret.mx = a.rval * (a.rval + 1ll) /2;        } else {            int h = a.rval - (ret.rcnt);            ret.mx =  a.rval * (a.rval + 1ll) /2 - h*(h+1ll)/2;        }        return ret;    }    ret.is_full=false;    if(a.is_full && a.lval == b.lval){        ret.lcnt = a.lcnt + b.lcnt;        ret.lval = a.lval;    } else {        ret.lcnt = a.lcnt;        ret.lval = a.lval;    }    if(b.is_full && b.rval == a.rval){        ret.rcnt = b.rcnt + a.rcnt;        ret.rval = b.rval;    } else {        ret.rval = b.rval;        ret.rcnt = b.rcnt;    }    ret.mx= max(a.mx,b.mx);    if(a.rval == b.lval ){        if(a.rval< a.rcnt + b.lcnt){            ret.mx = max(ret.mx, a.rval * (a.rval + 1ll) /2);        } else {            int h = a.rval - (a.rcnt + b.lcnt);            ret.mx = max(ret.mx, a.rval * (a.rval + 1ll) /2 - h*(h+1ll)/2);        }            }    return ret;}nod sgt[1201200];int arr[300300];int n,q;void build(int nd,int l,int r){    if(l==r){        sgt[nd].is_full=true;        sgt[nd].lcnt=1;        sgt[nd].rcnt=1;        sgt[nd].lval=arr[l];        sgt[nd].rval=arr[l];        sgt[nd].mx=arr[l];        return;    }    int mid=(r+l)/2;    build(2*nd,l,mid);    build(2*nd+1,mid+1,r);    sgt[nd]=merge(sgt[2*nd],sgt[2*nd+1]);}void update(int nd, int l, int r, int index){    if(r < index or index < l) return;    if(l==r and l == index){        sgt[nd].is_full=true;        sgt[nd].lcnt=1;        sgt[nd].rcnt=1;        sgt[nd].lval=arr[l];        sgt[nd].rval=arr[l];        sgt[nd].mx=arr[l];        return;    }    int mid=(r+l)/2;    update(2*nd,l,mid,index);    update(2*nd+1,mid+1,r,index);    sgt[nd]=merge(sgt[2*nd],sgt[2*nd+1]);    }nod query(int nd,int l,int r,int s,int e){    if(s<=l && r<=e){        return sgt[nd];    }    int mid=(r+l)/2;    bool isSet=false;    nod ret;    if(s<=mid){        ret=query(2*nd,l,mid,s,e);        isSet=true;    }    if(mid+1<=e){        if(isSet){            ret=merge(ret,query(2*nd+1,mid+1,r,s,e));        } else {            ret=query(2*nd+1,mid+1,r,s,e);        }    }    return ret;}signed main(){    cin >> n >> q;    assert(1 <= n and n <= 300000);    assert(1 <= q and q <= 300000);    for(int i = 1 ; i <= n ; i++){        cin >> arr[i];        assert(1 <= arr[i] and arr[i] <= 1000000);    }    build(1,1,n);    while(q--){        int type;        cin >> type;        assert(1 <= type and type <= 2);        if(type == 1)        {            int l,r;            cin >> l >> r;            assert(1 <= l and l <= r and r <= n);            assert(l<=r);            cout<<query(1,1,n,l,r).mx << " ";        }        else{            int x, v;            cin >> x >> v;            assert(1 <= x and x <= n);            assert(1 <= v and v <= 1000000);            arr[x] = v;            update(1,1,n,x);        }    }    cout << endl;}`