1473D - Program - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int INF=9e18;

int max(int a,int b){
    if(a>=b)return a;
    return b;
}
int min(int a,int b){
    if(a<=b)return a;
    return b;
}

class segment_tree_max{
    public:
    int n;
    vector<int> seg;
    segment_tree_max(int m){
        n=m;
        seg.resize(4*n,-INF);
    }
    //node is the index of segment tree and left is mostly 0 means starting of array and right is n-1 means last index
       int build(int node,int left,int right,vector<int> &nums){
        if(left==right){
            return seg[node]=nums[left];
        }
       int mid=(left+right)/2;
       int l=build(2*node+1,left,mid,nums);
       int r=build(2*node+2,mid+1,right,nums);
       return seg[node]=max(l,r);
    }
    //ind- segment tree ka index hai
    //l-intial start of segment array index means 0 in most cases 
    //r-> end of segment array index,n-1 index
     void Update(int ind,int l,int r,int indexToChange,int val){
         if(l==r){
             seg[ind]=max(seg[ind],val);
         }
         else{
             int mid=(l+r)/2;
             if(indexToChange<=mid && indexToChange>=l) Update(2*ind+1,l,mid,indexToChange,val);
             else
                 Update(2*ind+2,mid+1,r,indexToChange,val);
             //ek baar mera ind update hogya to uske upper ka sare ko update karna hoga kyuki wo bhi ussi range me aa rha hai
             seg[ind]=max(seg[2*ind+1],seg[2*ind+2]);
         }
    }
    
    
    //left,right mera query ka range hai and l,r mera segment tree me jitna element hai uska starting and last index hai
    int Query(int left,int right,int l,int r,int node){
        //completely inside
        if(l>=left && r<=right)
            return seg[node];
        //completely outside
        if(r<left || l>right)
            return -INF;
        //overalp me left right dono pe call
        int mid=(l+r)/2;
        int leftval=Query(left,right,l,mid,2*node+1);
        int rightval=Query(left,right,mid+1,r,2*node+2);
        return max(leftval,rightval);
    }

    void update(int idx,int val){
        Update(0,0,n,idx,val);
    }

    int query(int left,int right){
        return Query(left,right,0,n-1,0);
    }
};




class segment_tree_min{
    public:
    int n;
    vector<int> seg;
    segment_tree_min(int m){
        n=m;
        seg.resize(4*n,INF);
    }
    //node is the index of segment tree and left is mostly 0 means starting of array and right is n-1 means last index
       int build(int node,int left,int right,vector<int> &nums){
        if(left==right){
            return seg[node]=nums[left];
        }
       int mid=(left+right)/2;
       int l=build(2*node+1,left,mid,nums);
       int r=build(2*node+2,mid+1,right,nums);
       return seg[node]=min(l,r);
    }
    //ind- segment tree ka index hai
    //l-intial start of segment array index means 0 in most cases 
    //r-> end of segment array index,n-1 index
     void Update(int ind,int l,int r,int indexToChange,int val){
         if(l==r){
             seg[ind]=min(seg[ind],val);
         }
         else{
             int mid=(l+r)/2;
             if(indexToChange<=mid && indexToChange>=l) Update(2*ind+1,l,mid,indexToChange,val);
             else
                 Update(2*ind+2,mid+1,r,indexToChange,val);
             //ek baar mera ind update hogya to uske upper ka sare ko update karna hoga kyuki wo bhi ussi range me aa rha hai
             seg[ind]=min(seg[2*ind+1],seg[2*ind+2]);
         }
    }
    
    
    //left,right mera query ka range hai and l,r mera segment tree me jitna element hai uska starting and last index hai
    int Query(int left,int right,int l,int r,int node){
        //completely inside
        if(l>=left && r<=right)
            return seg[node];
        //completely outside
        if(r<left || l>right)
            return INF;
        //overalp me left right dono pe call
        int mid=(l+r)/2;
        int leftval=Query(left,right,l,mid,2*node+1);
        int rightval=Query(left,right,mid+1,r,2*node+2);
        return min(leftval,rightval);
    }

    void update(int idx,int val){
        Update(0,0,n,idx,val);
    }

    int query(int left,int right){
        return Query(left,right,0,n-1,0);
    }
};


void Solve(){
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    vector<int> pre(n,0);
    if(s[0]=='-')pre[0]=-1;
    else pre[0]=1;
    for(int i=1;i<n;i++){
        if(s[i]=='-')pre[i]+=pre[i-1]-1;
        else pre[i]+=pre[i-1]+1;
    }
    segment_tree_max maxi(n);
    segment_tree_min mini(n);
    maxi.build(0,0,n-1,pre);
    mini.build(0,0,n-1,pre);
    while(m--){
        int l,r;
        cin>>l>>r;
        int x,y,x1,y1;
        l--,r--;
        if(l>0){
            x=maxi.query(0,l-1);
            y=mini.query(0,l-1);
        }
        else{
            x=y=0;
        }
        x=max(0,x);
        y=min(0,y);
        if(r+1<n){
            x1=maxi.query(r+1,n-1);
            y1=mini.query(r+1,n-1);
        }
        else{
            x1=y1=0;
        }
        // cout<<n-1<<endl;
        // cout<<pre[]
        // cout<<x<<" "<<y<<endl;
        // cout<<x1<<" "<<y1<<endl;
        int val=0;
        if(r+1<n)val+=pre[r];
        if(l>0)
        val-=pre[l-1];
        x1-=val;
        y1-=val;
        x=max(x,x1);
        y=min(y,y1);
        cout<<x-y+1<<endl;
    }
}



int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
   
    int T=1;
    cin>>T;

    while(T--){
        Solve();
    }
    return 0;
}