Problem link : https://www.spoj.com/problems/GSS1/
IDEA: To solve this problem first we need to think where we can we get the maximum value in a range.Segment tree makes the problem easier to solve. But storing values in node is the tricky tasks here. Here each node must store more than one value. Maximum value in a range can be in left side or in right side or in both side. So, we will store four informtion in a node. They are total, left sum, right sum, best sum.Best value among these four value will be the answer.
Code:
#include <bits/stdc++.h>
#define min -9999999
#define mx1 (1<<16)
#define mx2 mx1<<2
#define endl '\n'
using namespace std;
struct val
{
long total,lsum,rsum,best;
};
val *segment = new val[mx2];
int *a = new int[mx1];
int maxof(int f, int g)
{
if(f>=g)
return f;
else
return g;
}
void simp(int pos)
{
segment[pos].total = segment[2*pos+1].total+segment[2*pos+2].total;
segment[pos].lsum = maxof(segment[2*pos+1].lsum,segment[2*pos+1].total+segment[2*pos+2].lsum);
segment[pos].rsum = maxof(segment[2*pos+2].rsum,segment[2*pos+2].total+segment[2*pos+1].rsum);
segment[pos].best = maxof(maxof(segment[2*pos+1].best,segment[2*pos+2].best),segment[2*pos+1].rsum+segment[2*pos+2].lsum);
}
void built(int lo,int hi,int pos)
{
if(lo==hi)
{
segment[pos].total= a[lo];
segment[pos].lsum= a[lo];
segment[pos].rsum= a[lo];
segment[pos].best= a[lo];
return;
}
int mid= lo+(hi-lo)/2;
built(lo,mid,2*pos+1);
built(mid+1,hi,2*pos+2);
simp(pos);
}
val query(int qlo,int qhi,int lo,int hi,int pos)
{
if(qlo>hi||qhi<lo)
{
return (val)
{
0,
min,
min,
min
};
}
if(qlo<=lo&&qhi>=hi)
{
return segment[pos];
}
int mid = lo+(hi-lo)/2;
val left=query(qlo,qhi,lo,mid,2*pos+1);
val right = query(qlo,qhi,mid+1,hi,2*pos+2);
val pr;
pr.total = left.total+right.total;
pr.lsum= maxof(left.lsum,left.total+right.lsum);
pr.rsum= maxof(right.rsum,right.total+left.rsum);
pr.best= maxof(maxof(left.best,right.best),left.rsum+right.lsum);
return pr;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
built(0,n-1,0);
int q;
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
x--,y--;
val res= query(x,y,0,n-1,0);
int ans=maxof(maxof(res.best,res.total),maxof(res.lsum,res.rsum));
cout<<ans<<endl;
}
return 0;
}
No comments:
Post a Comment