SpojGSS1.cpp

#include <bits/stdc++.h>
using namespace std;
class node{
	public: 
    		long long maxSum,prefixSum,suffixSum,sum;
		void setValue(int value){
			maxSum=prefixSum=suffixSum=sum=value;
		}
		void specifyNode(node &left,node &right){
			sum = left.sum+right.sum;
			prefixSum = max(left.prefixSum,left.sum+right.prefixSum);
			suffixSum = max(right.suffixSum,right.sum+left.suffixSum);
			maxSum = max(max(left.maxSum,right.maxSum),left.suffixSum+right.prefixSum);
		}
};

void build(int val,int low,int high,node *binVal,int *arr){
    if(low==high){
        binVal[val-1].setValue(arr[low]);
        return;
    }else{
        int mid = (low+high)/2;
        build(val*2,low,mid,binVal,arr);
        build(val*2+1,mid+1,high,binVal,arr);

        binVal[val-1].specifyNode(binVal[val*2-1],binVal[val*2]);
        return;
    }
}
node queryMax(node *binval,int val,int low,int high,int start,int end){
    if( end<low || high<start ){
        node jusnew;
        jusnew.setValue(INT32_MIN);
        return jusnew;
    }
    if(low>=start && high<=end){
        return binval[val-1];
    }
    int mid = (high+low)/2;
    node val1 = queryMax(binval,val*2,low,mid,start,end);
    node val2 = queryMax(binval,val*2+1,mid+1,high,start,end);
    node jusval;
    jusval.sum = val1.sum+val2.sum;
    jusval.prefixSum = max(val1.prefixSum,val1.sum+val2.prefixSum);
    jusval.suffixSum = max(val2.suffixSum,val2.sum+val1.suffixSum);
    jusval.maxSum = max(max(val1.maxSum,val2.maxSum),val1.suffixSum+val2.prefixSum);
    return jusval;
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    node binVal[n*4];
    build(1,0,n-1,binVal,arr);
   
    int m;
    cin >> m;
    while(m--){
        int start,end;
        cin >> start >> end;
        node just = queryMax(binVal,1,0,n-1,start-1,end-1);
        cout <<just.maxSum<< endl;
    }

	return 0;
}