I've been solving a problem and I found a solution, But I have to maintain some values.

So let's say you have an array and you have 2 types of queries, Which is, Change the value of an element, Add x to all values between l and r, Find the maximum prefix starting from l.

I know how to solve this problem without the range update, But i am stuck with the range update.

Any ideas how to solve this problem ?

Thanks in advance :)

https://cses.fi/problemset/task/1113 I was solving this problem from cses , I came up with an idea which is I can know the first ans last character of each string in the lexicographical sorted rotations which is.

The last characters is the input itself and the first characters is the sorted input

For example: (* represents an unknown character)

s = "cb#ab"

Then the lexicographical sorted rotations from the input are:

"****c"

"****b"

"****#"

"****a"

"****b"

And the sorted input is:

"#abbc"

So the first characters are:

"#****"

"a****"

"b****"

"b****"

"c****"

By combining i will have:

"#***c"

"a***b"

"b***#"

"b***a"

"c****b"

Basically I will construct a graph by adding a directed edge from first to last character of each string. The graph idea if x have a direct edge to y then y is before x in the answer string. So I can just find an Euler circuit which starts at '#' and ends at '#' and it will be the answer. But the problem with the idea is if there is a character which appears more than once. The logic may break because then you will have more than one choice to choose. But actually there should be a unique answer (all the choices are wrong except one but idk how to differentiate between them)

Any ideas to improve the answer or any other ideas to solve the problem ?

Thanks in advance :)

Recently I've read about minimum number of needed edges to construct SCC from a DAG. And it was the MAX(x,y) where x is the number vertices with 0 in-degree and y is the number of vertices with 0 out-degree. But i am wondering how to find such combination of edges in O(N) time. Thanks in advance :)

edit : solved. thank you very much for all people who helped me :)

i want to copy some problem from codeforces to polygon to do some changes on it to use it again on the gym do anyone know how to do that. Thanks in Advance.