MFQUE - Editorial

editorial
, , ,
1

MFQUE - Editorial

Problem Link:

Practice

Contest

Author, Tester and Editorialist:-
tejaram15

Difficulty:

Easy

Pre-Requisites:

Square root Decomposition.

Problem Statement:

Given an array and a range L to R. You need to find the Sum of squared differences of consequetive elements of the sorted range.

Explanation:

Applying Square root Decomposition Or Mo’s algorithm is easy here. It is an offline algorithm hence you need to store the queries and results.

Initially Sort the given ranges into sqrt(n) blocks according to the interval in which the starting index falls.

Secondly traverse through the queries and store the results in an efficient data structure like set in c++.

Now traverse through the set and calculate the required result.

Note: Remember Mo’s algorithm is not an optimization technique. It is just an ordering of queries which reduces the time complexity.(Proof of time complexity is given in the above editorial.)

Time complexity:

O(N*logN) (for sorting) + O(N*sqrt(N)) (for processing)

Solution : Here