GSS - Đoạn con có tổng lớn nhất

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#define MAX   50050
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
class SegmentTree {
private:
    struct Node {
        static const int INF=(int)1e9+7;
        int sum,left,right,all;
        Node() {
            sum=left=right=all=-INF;
        }
        Node(int x) {
            sum=left=right=all=x;
        }
        bool isNULL(void) const {
            return (all<=-INF);
        }
        Node operator + (const Node &x) const {
            if (isNULL()) return (x);
            if (x.isNULL()) return (*this);
            Node res;
            res.all=all+x.all;
            res.left=max(left,all+x.left);
            res.right=max(x.right,x.all+right);
            res.sum=max(max(sum,x.sum),right+x.left);
            return (res);
        }
    };
    int n;
    vector<Node> tree;
    void build(int a[],int i,int l,int r) {
        if (l>r) return;
        if (l==r) tree[i]=Node(a[r]);
        else {
            int m=(l+r)>>1;
            build(a,2*i,l,m);
            build(a,2*i+1,m+1,r);
            tree[i]=tree[2*i]+tree[2*i+1];
        }
        //printf("Tree %d (%d,%d): %d | %d | %d | %d\n",i,l,r,tree[i].all,tree[i].left,tree[i].right,tree[i].sum);
    }
    Node getMax(int i,int l,int r,int u,int v) const {
        if (l>v || r<u || l>r || v<u) return (Node());
        if (u<=l && r<=v) return (tree[i]);
        int m=(l+r)>>1;
        Node L=getMax(2*i,l,m,u,v);
        Node R=getMax(2*i+1,m+1,r,u,v);
        //printf("Get of %d (%d,%d): %d | %d |%d | %d\n",i,l,r,(L+R).all,(L+R).left,(L+R).right,(L+R).sum);
        return (L+R);
    }
public:
    SegmentTree() {
        n=0;
    }
    SegmentTree(int a[],int n) {
        this->n=n;
        tree.assign(4*n+7,Node());
        build(a,1,1,n);
    }
    int getMax(int l,int r) const {
        return (getMax(1,1,n,l,r).sum);
    }
};
int a[MAX],n,q;
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
}
void process(void) {
    SegmentTree myit(a,n);
    scanf("%d",&q);
    REP(zz,q) {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",myit.getMax(l,r));
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Download