BGQRS - Unofficial Editorial

My solution is \mathcal O(n \lg n) and passed in 0.47 seconds with some preprocessing. Idea is same as @zscoder described.

1 Like

You should see my solution if you are not very good in segment tree . good and easy solution to understand . i used basic concept (as zscoder described power of 2 and 5) . you can easily understand hows lazy working
Solution

3 Likes

I have tried to implement the Lazy Propagation on a Segment Tree to fetch the queries and update the values in O(logN). But my solution wasn’t accepted. Can someone help me out with where am I going wrong? PS: My code gives the correct output for the given test case and some random test cases. Here is my code.

1 Like

Here is comparatively short and clean implementation of **O (n lg n) ** solution based on segment-tree approach passed in 0.52 seconds. solution

8 Likes

can anyone suggest mistakes in my link text solution please??

And Why do we need to store the ex2,ex5,lz2,lz5?? can anyone please explain??

codechef is very slow in updating editorials

2 Likes

little complex… :slight_smile:

Here is my solution which uses single segment tree. It uses oops to further simplify the problem.Solution link

2 Likes

You can also see my solution too link :slight_smile:

2 Likes

My [solution][1]
[1]: CodeChef: Practical coding for everyone

is O(N log N) too with Segment Tree and Lazy Propagation, pass in 0.71 s.

Sure, also noticing that the second query can be transformed to first assigning sequence 1,2,… and then multiply it by Y can help a lot while handing that query. Lazy Propagation is something closer to the intended solution. Using sqrt blocks was too tempting for me, so I went for it - I see that we have similar run times, did you need to optimize your solution?

you sure the largest ?

Sqrt Decomposition is a nice trick and can help to solve many problems. Thanks for sharing!!
Can you suggest some good problems to start mastering this trick?

@pkacprzak My solution passed without fastio too, but fastio is slightly faster.

1 Like

@ankurverma1994 I added one bonus problem at the bottom of the editorial. It is perhaps the most classical one you can get.

1 Like

I tried to solve using same approach. I am getting WA. Please help. :slight_smile:

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

there is no need for a boolean(type2, in you code) to tell us whether reset is necessary or not. Notice you can simply set tree[node].st = -1 (for example) to indicate this node doesn’t require reset operation. Our solution are two much similar… hope we don’t find ourself in plagiarism :stuck_out_tongue: (LOL). couldn’t find the bug Yet.

And Why did you choose KMax as 20?
Thanks

@vishveshcoder As you can see, I set K (the initial size of a block) to be max(20, sqrt(n)). The constant 20 is chosen arbitrary. I did it in order to avoid extremely small blocks when sqrt(n) is small. Notice that later I set num_of_blocks = N / K. However, I think that you can just write K = sqrt(n) and everything should work just fine.

As your solution is too lengthy I can not read it completely but the thing is that your propagation of updates is not correct , for the test case-

1

7 6

1 2 3 4 5 6 7

1 2 6 5

2 2 7 1

1 2 5 2

3 1 4

3 3 7

3 2 6

your codes output is “6” but it should be “2” so simulate your codes
working on this test case and you will know the mistake.

4 Likes