# HackerEarth Update And Query problem solution

In this HackerEarth Update And Query problem, Deepankar loves to play with the arrays a lot. Today, he has an array A of N integers. He has to fulfill M operations. Each operation has one of the following two types:

U X Y : Update the value at the Xth index of the array with Y.

Q X C : Calculate the length of the longest subarray that starts at Xth index and satisfy following inequality

A[X]-C ≤ V ≤ A[X] + C
Where V is any value from the chosen subarray.
Deepankar is facing difficulty in maintaining the efficiency of the operations. Can you help him in accomplishing this task efficiently.

## HackerEarth Update And Query problem solution.

`#include <bits/stdc++.h>using namespace std ;#define MAXN 100001#define ft first#define sd second int N,M,A[MAXN],STMX[4*MAXN],STMN[4*MAXN],X,Y,C;char str[10] ;void buildst(int idx,int ss,int se){    if(ss == se){        STMX[idx] = A[ss] ;        STMN[idx] = A[ss] ;        return ;    }    int mid = (ss + se)/2;    buildst(2*idx,ss,mid) ;    buildst(2*idx+1,mid+1,se) ;    STMX[idx] = max(STMX[2*idx],STMX[2*idx+1]) ;    STMN[idx] = min(STMN[2*idx],STMN[2*idx+1]) ;}void update(int idx,int ss,int se,int val,int pos){    if(ss == se){        STMX[idx] = val ;        STMN[idx] = val ;        return ;    }    int mid = (ss + se)/2 ;    if(pos <= mid)        update(2*idx,ss,mid,val,pos) ;    else        update(2*idx+1,mid+1,se,val,pos) ;        STMX[idx] = max(STMX[2*idx],STMX[2*idx+1]) ;    STMN[idx] = min(STMN[2*idx],STMN[2*idx+1]) ;}pair<int,int> query(int idx,int ss,int se,int l,int r){    pair<int,int> ret ;    if(l > se || r < ss){        ret.ft = INT_MIN ;        ret.sd = INT_MAX ;        return ret ;        }    if(l <= ss && se <= r){        return make_pair(STMX[idx],STMN[idx]) ;    }    int mid = (ss + se)/2 ;    pair<int,int> left ,right ;    left  = query(2*idx,ss,mid,l,r) ;    right = query(2*idx+1,mid+1,se,l,r) ;    return make_pair(max(left.ft,right.ft),min(left.sd,right.sd)) ;}bool check(int L,int R,int C){    pair<int,int> ret ;    ret = query(1,1,N,L,R) ;    return ((ret.ft-A[L] <= C) && (A[L]-ret.sd <= C)) ;}void solve(int X,int C){    int V1,V2 ;    V1 = V2 = -1 ;    if(C >= 0){        int low , high , mid ;        low = X ;        high = N ;        while(low <= high){            mid = (low + high)/2 ;            bool f = check(X,mid,C) ;            if( f && (mid == N || check(X,mid+1,C) == 0)){                break ;            }else if(f){                low = mid+1 ;            }else{                high = mid-1 ;            }        }        V1 = mid-X+1 ;        pair<int,int> ret = query(1,1,N,X,mid) ;         V2 = max(ret.ft-A[X],A[X]-ret.sd) ;    }    printf("%d %d\n",V1,V2) ;   }int main(){    scanf("%d%d",&N,&M) ;    assert(N >= 1 && N <= 100000) ;    assert(M >= 1 && M <= 200000) ;    for(int i=1;i<=N;i++){        scanf("%d",&A[i]) ;        assert(A[i] >= 1 && A[i] <= 1000000000) ;       }       buildst(1,1,N) ;    while(M--){        scanf("%s",str+1) ;        if(str[1] == 'U'){            scanf("%d%d",&X,&Y) ;            A[X] = Y ;            update(1,1,N,Y,X) ;            }else if(str[1] == 'Q'){            scanf("%d%d",&X,&C) ;            solve(X,C) ;                    }else{            assert(0) ;        }    }    return 0 ;}`