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;
}