MAXBTY - Editorial

i tried that way,my query working fine but update is not,shall we discuss more on BIT for this problem?

I tried the logic of editor’s solution and implemented it in Python. Can anybody tell me why am I getting TLE for my solution.
Link to my solution

//Can anyone tell me what is wrong in this solution?
def make_list(A,N,L,R):
s=0
r=0
L.append(A[0])
R.append(A[N-1])
for i in range(1,N):
if L[i-1]>0:
L.append(A[i]+L[i-1])
else:
L.append(A[i])
if R[0]>0:
R.insert(0,A[N-1-i]+R[0])
else:
R.insert(0,A[N-1-i])

T=int(input())
for t in range(T):
L=[]
R=[]
N,Q=map(int,input().split())
A=[int(x) for x in input().split()]
make_list(A,N,L,R)
for q in range(Q):
v,x,y=input().split()
if v==‘Q’:
x,y=int(x),int(y)
s=0
for i in range(x,y-1):
s=s+A[i]
s=s+L[x-1]+R[y-1]
print(s)
elif v==‘U’:
x,y=int(x),int(y)
A[x-1]=y
L=[]
R=[]
make_list(A,N,L,R)

@tmwilliamlin

there is very small and easy implementation
https://www.codechef.com/viewsolution/30709921
could somebody help me !!! i am getting wrong ans.

You are not updating the tree according to its lazy values when you perform querymin().

In Setter’s Solution,
in queryMin function why is it that we have to return 0, if the STnode’s range is not inside the query interval of (i,j) ?
if we return 0 , then wouldn’t the returned zero affect the further actual querying ?

That is, if size of array is 5 and we call queryMin for (4,5) interval… the queryMin call for (1,3) returns 0 and if the minimum value returned by queryMin for (4,5) interval is +ve ; then the final answer will be given as 0 as the minimum value.
I checked that this code returns 0 instead of the actual positive value which was supposed to come.

So, shouldn’t the value returned for out of range condition be changed to infinity?
But that’s what i did(exactly same as that of setter’s solution except for what i return) , getting some wrong answer for the sample test cases itself.

correct me if I’m wrong.

Is my basic logic is wrong?
if not i am getting wrong answer.

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin >> t;
while (t--)
{
    int n, q, x, y;
    cin >> n >> q;
    char query;
    int arr[n];
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    while (q--)
        {
            cin >> query >> x >> y;
            int xIndex = x - 1;
            int yIndex = y - 1;
            if (query == 'Q') {
                int tmpsum = 0, lmax = 0, rmax = 0, sum = 0;
                
                //left side max sum
                for (int i = xIndex -1; i >= 0; i--)
                {
                    if (lmax < tmpsum + arr[i])
                    {

                        lmax = tmpsum + arr[i];
                    }
                    tmpsum += arr[i];
                }
                tmpsum = 0;
                
                //right side max sum
                for (int i = yIndex + 1; i < n; i++)
                {
                    if (rmax < tmpsum + arr[i])
                    {
                        rmax = tmpsum + arr[i];
                    }
                    tmpsum += arr[i];
                }
                
                //sum between x and y
                for (int i = xIndex; i <= yIndex; ++i)
                {
                    sum += arr[i];
                }
                
                //max sum
                sum += rmax + lmax;
                cout << sum << "\n";
            } else {
                arr[xIndex] = y;
            }
        }
}

return 0;

}

Can you help me? Whats wrong with this?

Solution : https://www.codechef.com/viewsolution/30716889

What is negative prefix sum?

When each element of prefix sum array is multiplied by -1, we get the negative prefix sum array

Instead of maintaining 2 segment trees, i maintained values of segment sum (z), maximum prefix (y) and maximum suffix sum (x) at each node in the segment tree, then output max(z,x+z,y+z,x+y+z) . But I am getting a WA. Is my logic incorrect? Please help me find what’s wrong with my code: https://www.codechef.com/viewsolution/30749140

@tmwilliamlin
Can some one please reply?

Read my this post .
unofficial short editorial

1 Like

@jugshaurya william lin has explained the mysara solution on his youtube channel.

Link : https://www.youtube.com/watch?v=wYfp3ViLC-s&t=20s

#include<bits/stdc++.h>
#define maxn 100001
#define maxt 500005
using namespace std;

struct node
{
	long long x;
	long long n;
};

struct node tree[maxt];


long long max(long long a,long long b)
{
	if(a>b) return a;
	else return b;
}

long long min(long long a,long long b)
{
	if(a>b) return b;
	else return a;
}

node build(long long pre[],int v,int l,int r)
{
	if(l==r)
	{
		tree[v].x=pre[l];
		tree[v].n=pre[l];
		return tree[v];
	}
	else
	{
		node m1,m2;
		int mid = (l+r)/2;
		m1 = build(pre,2*v,l,mid);
		m2 = build(pre,2*v+1,mid+1,r);
		tree[v].x=max(m1.x,m2.x);
		tree[v].n=min(m1.n,m2.n);
		return tree[v];
	}
}



long long Qx(int v,int l,int r,int x,int y)
{
	if(l==x&&r==y)
	{
		return tree[v].x;
	}
	int mid = (l+r)/2;
	if(y<=mid)
	{
		return Qx(2*v,l,mid,x,y);
	}
	if(x>mid)
	{
		return Qx(2*v+1,mid+1,r,x,y);
	}
	return max(Qx(2*v,l,mid,x,mid),Qx(2*v+1,mid+1,r,mid+1,y));
}

long long Qn(int v,int l,int r,int x,int y)
{
	if(l==x&&r==y)
	{
		return tree[v].n;
	}
	int mid = (l+r)/2;
	if(y<=mid)
	{
		return Qn(2*v,l,mid,x,y);
	}
	if(x>mid)
	{
		return Qn(2*v+1,mid+1,r,x,y);
	}
	return min(Qn(2*v,l,mid,x,mid),Qn(2*v+1,mid+1,r,mid+1,y));
}

node ux(int v,int l,int r,int x,long long add,long long pre[])
{
	int mid=(l+r)/2;
	if(l==r&&l>=x)
	{
		pre[l]+=add;
		tree[v].x=pre[l];
		tree[v].n=pre[l];
		return tree[v];
	}
	if(x>=mid+1)
	{
		node m1=tree[2*v];
		node m2=ux(2*v+1,mid+1,r,x,add,pre);
		tree[v].x = max(m1.x,m2.x);
		tree[v].n = max(m1.n,m2.n);
		return tree[v];
	}
	node m1,m2;
	m1=ux(2*v,l,mid,x,add,pre);
	m2=ux(2*v+1,mid+1,r,x,add,pre);
	tree[v].x = max(m1.x,m2.x);
	tree[v].n = max(m1.n,m2.n);
	return tree[v];
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,q;
		cin>>n;
		cin>>q;
		long long b[n+1]={0};
		long long pre[n+1]={0};
		for(int i=1;i<=n;++i)
		{
			cin>>b[i];
			pre[i]=b[i]+pre[i-1];
		}
		build(pre,1,1,n);
		while(q--)
		{
			char w;
			cin>>w;
			if(w=='Q')
			{
				int x,y;
				cin>>x>>y;
				long long a,b;
				a=Qx(1,1,n,y,n);
				b=Qn(1,1,n,1,x-1);
				if(b>0) b=0;
				cout<<a-b<<endl;
			}
			else
			{
				int x;
				long long y;
				cin>>x;
				cin>>y;
				long long add;
				add=y-b[x];
				ux(1,1,n,x,add,pre);
			}
		}
	}
	return 0;
}

I have used segmented tree then also it is showing time limit exceeded. Please help, how can I optimize it further?

@jprm2 thanks bhai

Please tell me what is wrong in my code:

https://www.codechef.com/viewsolution/30761682

My Code is almost similar to setters code,thats why am asking

Please help guys
@tmwilliamlin @imanik @ezio_26 @everule1

Can , someone please explain the example input in the question ?
5 5
-1 2 -2 1 -3
How in the first query - Q 3 5 , the output is -2
and in the fifth query - Q 3 5 the output is -1 ?

That helped. Thanks!

I guess no, cause segment tree does updates and queries both in logN time while update in dp will take O(N) time.