Query regarding Online MO algorithm

How MO’s algorithm is used when present query parameter depends on the answer of previous one?

You cant use MO if queries are online.
MO is an offline algorithm.

1 Like

In the editorial of COOLCHEF, it is mention that sub-task 3 can be solve by using online variant of MO algorithm. Since Queries are encoded in problem, then how MO is used to solve it?

Subtask 3 has L_1=R_1=0. So the queries are (0 \cdot a + L_2, 0 \cdot a+R_2) = (L_2,R_2) so they don’t depend on the previous one.

What exactly is an MO algorithm?

Ohh sorry, I didn’t noticed that. Thanks :raised_hands:

Its an algorithm used for solving Range query question like for given query you have to find the sum for elements of given range. This video might help you understand the same.

1 Like

L1 = R1 =0 is in subtask2, not in subtask3.

I have same question how solve subtask3 using Mos algorithm.

In editorial mention that,“subtask3 can be solve using Online Mo’s algorithm”.

how ??

Nope @psaini72, it is mentioned in editorial that subtask 3 can be solved by using Online variant of MO algo. So how to solved it?

Sorry about that. Did not read it carefully. Maybe you’ll have better luck asking this on the editorial page itself. The editorialist will probably see that instead of this topic.

Edit: There is a resource to that right next to where it is mentioned. If you need help understanding that resource then the best thing for you right now is delete this topic and start over. This one is full of bad replies. I am going to delete my replies on this.

This is partially our fault too but I am going to blame it fully on @sagar2406. Next time provide some context : “I was looking at the editorial for COOLCHEF and found this resource and I need help understanding it” etc. That’s what the description is for.

2 Likes

You are right @psaini72, I should ask this question on editorial page and I will take care from next time and provide relevant context.:slightly_smiling_face:
Actually when i read the editorial, i was thought that MO algorithm can be applied when queries are encoded. I read the resources that was mentioned in the editorial but didn’t got any clue on how to solve by using online MO, that why i start a new topic.

https://www.codechef.com/viewsolution/24717920 Here’s my solution using online Mo’s algorithm for 80 points.

1 Like