I am trying to solve E. Addition to Segment but for some reason I keep getting wrong answer on test case 3.You can see my code here. The weird thing is that when I change my set() function to the following:
void set(ll i, ll v, ll x, ll lx, ll rx)
{
if(i>=rx || i<lx) return;
if(rx-lx==1)
{
values[x]+=v;
return;
}
int m=(lx+rx)/2;
set(i,v,2*x+1,lx,m);
set(i,v,2*x+2,m,rx);
values[x]=merge(values[2*x+1], values[2*x+2]);
return;
}
I get WA on testcase 63 (instead of testcase 3). This makes no sense to me because the two implementations of the set function should be logically equivalent. What is going on here?
Added this at the begging of your set function and now its AC.
Its up to you to figure out why :)
When the right border of the segment we want to change is n, the program will try to substract from the element with index n which is out of bounds. That line is to prevent this. Is this why?
Lol, indeed. First of all I thought that's solves the problem because set sometimes go in wrong direction, but this theory was declined because there's is ifs in your code that already prevent it. So, I just wrote "Its up to you to figure out why :)" to make it looks like I know why it works. But yeah, you don't need this if statement actually, you can just make segtree of size n+1, instead of n, and it will fix the bug.