GSS1

                                                     GSS1

                                                                segment tree

Problem Link

#include <iostream>

#include <stdio.h>

using namespace std;

struct node

{

    long bestSum, leftSum, rightSum, totalSum;

};

int n;

long t;

node seg[200003];

long arr[50003];

node combine(node &lc, node &rc)

{

    node temp;

    temp.totalSum = lc.totalSum + rc.totalSum;

    temp.leftSum = max(lc.leftSum, lc.totalSum + rc.leftSum);

    temp.rightSum = max(rc.rightSum, rc.totalSum + lc.rightSum);

    temp.bestSum = max(lc.rightSum + rc.leftSum, max(lc.bestSum, rc.bestSum));

    return temp;

}

void buildTree(int l, int r, int index)

{

    if(l == r)

    {

        seg[index].bestSum = seg[index].rightSum = seg[index].leftSum = seg[index].totalSum = arr[l];

    }

    else

    {

        int mid =  l + ((r - l) >> 1);

        int lchild = (index << 1) + 1;

        int rchild = (index << 1) + 2;

        buildTree(l, mid, lchild);

        buildTree(mid + 1, r, rchild);

        seg[index] = combine(seg[lchild], seg[rchild]);

    }

}

node query(int l, int r, int qs, int qe, int index)

{

    if(qs <= l && qe >= r)

        return seg[index];

    int mid = l + ((r - l) >> 1);

    int lchild = (index << 1) + 1;

    int rchild = (index << 1) + 2;

    if(qe <= mid)

        return query(l, mid, qs, qe, lchild);

    if(qs > mid)

        return query(mid + 1, r, qs, qe, rchild);

    node lc = query(l, mid, qs, qe, lchild);

    node rc = query(mid + 1, r, qs, qe, rchild);

    return combine(lc, rc);

}

int main()

{

    int m, x, y;

    scanf("%d",&n);

    for(int i = 0; i < n; i++)

        scanf("%ld",&arr[i]);

    buildTree(0, n - 1, 0);

    scanf("%d",&m);

    for(int i = 0; i < m; i++)

    {

        scanf("%d",&x);

        scanf("%d",&y);

        t = query(0, n - 1, x - 1, y - 1, 0).bestSum;

        printf("%ld\n", t);

    }

    return 0;

}