spoj GSS1 problem

general
41

@meooow = ShaktiBilli (I call him that) :stuck_out_tongue: :smiley: :wink: XD

2 Likes
42

@meooow @neilit1992 for the ans of any query we are checking if (l > mid) or if (r <= mid) why are we doing this

 int mid = (start+end)/2;
if (l > mid)
   return query(2*index+2, mid+1, end, l, r);
if (r <= mid)
   return query(2*index+1, start, mid, l, r);

node left = query(2*index+1,start,mid,l,r);
node right = query(2*index+2,mid+1,end,l,r);
43

@meooow for the ans of any query we are checking if (l > mid) or if (r <= mid) why are we doing this check below i have added the sample code

44

if (l > mid) return query(2*index+2, mid+1, end, l, r);
In this part if l>mid, then values below mid are irrelevant so we check for values only above mid, ie, mid+1 to end. And if l>mid then r must be greater than mid.

if (r <= mid) return query(2*index+1, start, mid, l, r);
In this part r<=mid so values above mid are irrelevant. And if r<=mid then l must be below r and hence below mid.

You can match this idea to that of binary search, in terms, that we are discarding irrelevant positions ie, positions that won’t affect our query or computation.

1 Like
45

but if i am removing these two lines code is giving me the wrong answer

46

If you remove that part of code you need to use

node left = query(2*index+1,start,mid,l,min (mid,r)); node right = query(2*index+2,mid+1,end,max(l,mid+1),r);

This should work, though I don’t use it coz it may be prone to error sometimes

47

can you explain why…i am very confused with this

48

http://e-maxx.ru/algo/segment_tree This link explains this, though I’ve implemented this way but it gives WA in test case 9 probably we need to take care of edge cases

49

can anybody tell why it is giving wrong answer if i remove line number 70 to 73

50

@anno you can have a look on this video tutorial to clear your doubts regarding Segment Trees.

Here’s the Link

Now as far as your question is concerned,

l and r are the intervals in which we have to make query on the segment tree.

Also start to mid and mid+1 to end are the two segments in which we have divided the current interval(i.e. start to end). Now start to mid will be in the left child of current node and mid+1 to end will be in the right child of current node.

Now it should be clear that in your code if l>mid, then we don’t have to query on the left child of current node, that’s why we simply moved to position 2*pos+2 (right child).

Similarly, if r<=mid then we can straightaway move to the left child of current node, that is why you did set the position there to 2*pos+1

Hope this helps. If you have any other doubts please comment below. :slight_smile:

51

see if i remove that line number 70 to 73 its giving wrong answer…why?

52

@meooow @neilit1992 @anno

I am getting TLE, can you please look into it.

https://pastebin.com/jyuhAm22

53

The best explanation I got on Google.link

54

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;
ll arr[50005];
struct Tree{
ll pre,su,tot,bst;
}tree[200005];
void build_tree(ll node,ll a,ll b)
{
if(a==b)
{
tree[node].pre=arr[a];
tree[node].su=arr[a];
tree[node].tot=arr[a];
tree[node].bst=arr[a];
return;
}
ll mid=(a+b)>>1;
build_tree(node2,a,mid);
build_tree(node2+1,mid+1,b);
tree[node].pre=max(tree[node2].pre,tree[node2].tot+tree[node2+1].pre);
tree[node].su=max(tree[node2+1].su,tree[node2+1].tot+tree[node2].su);
tree[node].tot=tree[node2].tot+tree[node2+1].tot;
tree[node].bst=max(tree[node2].su+tree[node2+1].pre,max(tree[node2].bst,tree[node2+1].bst));
}
Tree query_tree(ll node, ll a ,ll b, ll i,ll j)
{
Tree t;
if(a>b||a>j||b<i)
{
t.pre=t.su=t.bst=INT_MIN;
t.tot=0;
return t;
}
if(a>=i&&b<=j)
return tree[node];
ll mid=(a+b)>>1;
Tree q1=query_tree(node2,a,mid,i,j);
Tree q2=query_tree(node2+1,mid+1,b,i,j);
t.pre=max(q1.pre,q1.tot+q2.pre);
t.su=max(q2.su,q2.tot+q1.su);
t.tot=q1.tot+q2.tot;
t.bst=max(q1.su+q2.pre,max(q1.bst,q2.bst));
return t;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>arr[i];
build_tree(1,1,n);
ll q;
cin>>q;
while(q–)
{
ll l,r;
cin>>l>>r;
Tree a=query_tree(1,1,n,l,r);
cout<<a.bst<<"\n";
}
}