KnightKnight's blog

By KnightKnight, history, 13 months ago,

With Atcoder API of Lazy Segment Tree, Lazy Seg Tree Template
I am trying the problem where we need to support query to increment a range with a given value.

The Atcoder API implementation seems to fail here, where I have an array.

[3, 2, 4, 5, 1, 1, 5, 3]

and I want to do a range update over the range [1,4] ( 0 based indexing) and add a value 1 to it.
The sum should ideally change to 16 after the update and the array should look like

[3, 3, 5, 6, 2, 1, 5, 3]

The query function , the .prod() function of Atcoder API seems to return result 15,
You can try running this code for your reference to understand the ambiguity happening here.

Code
Output

I am using CPP20 and I am pretty sure (almost 99%) that it is a bug in their implementation,
just want someone to acknowledge it or maybe tell what am I missing here.
cc yosupo

UPD -> It is resolved but yeah things are kinda confusing with this template.

UPD 2-> This template is quite useful if you ever gone through the Polynomial queries question in CSES section about adding AP to a range . It is one among the toughest ones.

Here is the complete structure to AC it using AtCoder Template.

Polynomial Queries CSES
• -8

By KnightKnight, history, 3 years ago,

In case you are not aware about ICPC regionals happening here is the link to see the information :D https://www.amrita.edu/icpc21

• +1

By KnightKnight, history, 4 years ago,

This is the link for the question. But I will state the question here as well as this task gives us a string of digits in which we have to find number of substrings that are divisible by 2019, I have tried with the editorial but one thing seems to be ambiguous and I am not able to reason it out this line states that " 2019 is not divisible by 2 or 5, so there exists the inverse of 10 in mod2019. So 10n is a multiple of 2019 if and only if n is a multiple of 2019" What is the inverse helping us out in finding divisibility for substrings It will be a great help if some one could clear my doubts

UPD My doubt is clear now ! Errichto Helped with his video on his channel about the same question.

• +1