Segment tree beats, Tima's problemset

Информатика
1

Здравствуйте, возник вопрос по задаче Login - Codeforces , где мое решение берет ВА на 7 тесте

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define F first
#define S second
ll INF=1e18;
vector <ll> val(3000003,-INF);
vector <ll> mxa(8000008,-INF);
vector <ll> mxb(8000008,-INF);
vector <ll> lza(8000008,0);
void build(ll v,ll tl,ll tr)
{
	if(tl==tr)
	{
		mxa[v]=val[tl];
		mxb[v]=val[tl];
		return;
	}
	ll tm=(tl+tr)/2;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
	mxa[v]=max(mxa[v*2],mxa[v*2+1]);
	mxb[v]=max(mxb[v*2],mxb[v*2+1]);
}
void push(ll v,ll tl,ll tr)
{
	if(!lza[v]) return;
	if(tl!=tr)
	{
		mxa[v*2]+=lza[v];
		mxa[v*2+1]+=lza[v];
		mxb[v*2]=max(mxa[v*2],mxb[v*2]);
		mxb[v*2+1]=max(mxa[v*2+1],mxb[v*2+1]);
		lza[v*2]+=lza[v];
		lza[v*2+1]+=lza[v];
	}
	lza[v]=0;
}
void update(ll v,ll tl,ll tr,ll l,ll r,ll value)
{
	push(v,tl,tr);
	if(r<tl || l>tr) return;
	if(l<=tl && tr<=r)
	{
		push(v,tl,tr);
		lza[v]+=value;
		mxa[v]+=value;
		mxb[v]=max(mxb[v],mxa[v]);
		return;
	}
	ll tm=(tl+tr)/2;
	update(v*2,tl,tm,l,r,value);
	update(v*2+1,tm+1,tr,l,r,value);
	mxa[v]=max(mxa[v*2],mxa[v*2+1]);
	mxb[v]=max(mxb[v*2],mxb[v*2+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r)
{
	push(v,tl,tr);
	if(r<tl || l>tr) return -INF;
	if(l<=tl && tr<=r)
	{
		push(v,tl,tr);
		return mxb[v];
	}
	ll tm=(tl+tr)/2;
	ll res=max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	mxa[v]=max(mxa[v*2],mxa[v*2+1]);
	mxb[v]=max(mxb[v*2],mxb[v*2+1]);
	return res;
}
int main()
{
	freopen("max.in","r",stdin);freopen("max.out","w",stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>val[i];
	}
	build(1,1,n);
	ll q;
	cin>>q;
	for(ll i=1;i<=q;i++)
	{
		ll temp,l,r,x;
		cin>>temp>>l>>r;
		if(temp==1)
		{
			cin>>x;
			update(1,1,n,l,r,x);
		}
		else
		{
			cout<<get(1,1,n,l,r)<<"\n";
		}
	}
	return 0;
}
/*
*/

Почему?

2 лайка
2

@eudaimon can you identify any bugs in Mansur’s code? Point to specific lines. Can you identify any errors/other issues in the logic of the approach? Be very specific.

1 лайк
3

Certainly, @Anton. Let’s take a closer look at MansurL’s code to identify possible issues.

  1. In the push function, the lazy propagation seems to be applied only when tl!=tr. However, the propagation should be done unconditionally before further updates or queries to ensure that the current node’s value is accurate. This might be the cause of the wrong answer.

  2. In the update function, after recursively updating the left and right children, the lazy values lza[v*2] and lza[v*2+1] are updated, but the push function is not called again to propagate those updates to the grandchildren. This may lead to incorrect value propagation and ultimately, incorrect segment tree values.

  3. In the get function, there’s a call to push(v,tl,tr); inside the condition checking if(l<=tl && tr<=r). This seems redundant since the push function is already called at the beginning of the get function.

  4. The push function is also missing an implementation to update the mxb values for the children nodes after applying the lza value. This could also contribute to incorrect values during queries.

  5. In the update function, when the segment of update fully covers the current segment of the node, the current node is updated and so are its lazy values, but the function returns immediately after setting the lazy value. It should instead call push to the children to ensure that the lazy values are propagated down the tree.

Correcting these issues might fix the problem with the wrong answer on test 7. It’s essential to carefully manage the lazy propagation to ensure that all updates are correctly applied and that the segment tree reflects the true state after each update.

1 лайк
4

Incorrect

1 лайк
5

I apologize for the misunderstanding, @MansurL. Let’s try another approach to debug your code:

  1. Lazy Propagation:

    • The push function does not propagate the lazy value to the children nodes correctly. When tl != tr, it should propagate the lazy value to both lza[v*2] and lza[v*2+1] before updating mxa[v*2] and mxa[v*2+1]. The current implementation updates mxa and mxb before ensuring the children are correctly updated with the lazy values.

  2. Update Function:

    • Within the update function, after the condition if(l<=tl && tr<=r), the current segment is updated, and the function returns immediately. However, before returning, the push function should be called for the children nodes to ensure the updates are properly propagated.

  3. Query Function:

    • The get function also seems to have an incorrect propagation of the lazy values. The push function is called at the beginning, which is correct, but then it is called again inside the condition if(l<=tl && tr<=r). This second call is not needed since the lazy values for the current node have already been propagated.

  4. Memory Allocation:

    • The sizes of the vectors val, mxa, mxb, and lza are fixed and quite large. Make sure these sizes are indeed required for the problem constraints and that they do not cause any memory issues.

  5. General Logic:

    • Ensure that the segment tree is correctly initialized, as incorrect initialization may lead to issues during the update and query phases.

  6. Input/Output:

    • The code uses freopen to redirect input and output. Check whether the problem environment expects this or if it should use standard input/output streams.

Please review these points in your code and see if addressing them resolves the issue with test 7. Debugging can often be a process of trial and error, so it’s important to carefully test each change to identify what may be causing the wrong answer.

1 лайк
6

image
image1136×740 42 KB

1 лайк
7

It appears @MansurL has provided a screenshot or an image, presumably related to the problem at hand. Unfortunately, as a text-based AI, I’m unable to view or interpret images directly.

If the image contains code, error messages, or other textual information, could you please provide that information in text form? This will allow me to assist you further with debugging the issue. If it’s an error message or test case output, please copy and paste the text here. If it’s a diagram or visual aid explaining the segment tree or related concepts, please describe it as best as you can in words.

1 лайк
8

Тут помимо хранения lazy[v], нужно хранить еще максимальный lazy[v], который был и потом пытаться обновлять mxa[v], mxb[v] с помощью него.

У тебя на таком тесте не работает(я застрессил):

7

-10 -3 -2 0 7 -2 -5

7

1 5 7 1

1 1 7 -7

2 7 7

1 6 6 1

2 4 5

2 1 3

1 2 5 -3

Ответ должен быть:
-4

8

-2

У тебя:

-5

7

-2

2 лайка