chimic_eu_nu_gata

#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream fin("chimic.in");///nu-i ok
ofstream fout("chimic.out");
struct interval
{
    int s, d;
};
interval b[NMAX];
int n, a[NMAX], S, sm;
int max3(int a,int b,int c)
{
    return max(max(a,b),c);
}

struct segNode
{
    int left, right, segsum, bestsum;
};
segNode tree[4*NMAX];
void merge(segNode &node,segNode &cl,segNode &cr)
{
    node.segsum = cl.segsum+cr.segsum;
    node.left = max(cl.segsum+cr.left,cl.left);
    node.right = max(cr.segsum+cl.right,cr.right);
    node.bestsum = max3(cl.bestsum,cr.bestsum,cl.right+cr.left);
}

void build(int node,int tl,int tr)
{
    if(tl==tr)
    {
        tree[node].left=tree[node].right=tree[node].segsum=tree[node].bestsum=a[tl];
        return;
    }
    int cl = node<<1;
    int cr = cl|1;
    int tm = (tl+tr)>>1;
    build(cl,tl,tm);
    build(cr,tm+1,tr);
    merge(tree[node],tree[cl],tree[cr]);
}

void query(segNode &res,int node,int tl,int tr,int l,int r)
{
    if(tl==l and tr==r)
        res=tree[node];
    else
    {
        int cl=node<<1;
        int cr = cl|1;
        int tm= (tl+tr)>>1;
        if(r<=tm)
            query(res,cl,tl,tm,l,r);
        else if(l>tm)
            query(res,cr,tm+1,tr,l,r);
        else
        {
            segNode leftNode,rightNode;
            query(leftNode,cl,tl,tm,l,tm);
            query(rightNode,cr,tm+1,tr,tm+1,r);
            merge(res,leftNode,rightNode);
        }
    }
}
int main()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    for(i=1;i<=n;i++)
        fin>>b[i].s>>b[i].d;
    build(1,1,n);                  /// se construieste segment tree
    /**for(i=1;i<=n;i++)
        cout<<tree[i].left<<" "<<tree[i].right<<" "<<tree[i].segsum<<endl;*/
    for(i=1;i<=n;i++)  /// asta-i ca un fel de interogare pentru sume
    {
        if(b[i].s==-1)
            break;
        segNode res;
        query(res,1,1,n,b[i].s,b[i].d);
        cout<<res.bestsum<<endl;
    }
    return 0;
}