PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:MediumHard PREREQUISITES:MO's algorithm PROBLEM:
QUICK EXPLANATION:
EXPLANATION:SUBTASK 1In the first subtask, both $N$ and $M$ are quite small, up to $200$, so the most straightforward solution will work here. For each query $[L, R]$, make a copy of a segment $A[L, R]$, sort it, and compute the result using the equation given in the statement. If you use a quadratic time sorting algorithm, the solution has running time $O(M \cdot N^2)$ which is enough here. SUBTASK 2In the second subtask, $N$ and $M$ can be up to $10^4$. We can solve the problem with these constraints, if we replace a quadratic time sorting algorithm with $O(N \cdot \log N)$ method, and implement the solution efficiently, using static allocated memory. The total time complexity of this method is $O(M \cdot N \cdot \log N)$. SUBTASK 3
Let $pos[k]$ be the sorted vector of indices at which element with value $k$ occurs in $A$. There are at most $100$ such vectors, and we can compute all of them in $O(N)$ time. Now, in order to handle a single query $[L, R]$, we iterate over all possible values from $0$ to $100$, and check if a particular value $v$ occurs at positions from $L$ to $R$ at least once. This can be done by a binary search on $pos[v]$. Then, in order to compute the result, we can just compute it using only single occurrences of values of elements in $A[L, R]$, which we just have computed. This is sufficient, because if a certain value $v$ occurs more than once in $A[L, R]$, any of these addition occurrences do not have any impact on the result, because they are consecutive elements in a sorted segment $A[L, R]$, so they add nothing to the sum, because $(v  v)^2 = 0$. The total time complexity of this method is $O(N + M \cdot 100 \cdot \log N)$ SUBTASK 4
At the first sight, the problem look really complicated. It is not clear how to figure out the solution for one query knowing the solution for an other one, due to computing their sums in a sorted order. However, we do not have to answer these queries one by one, i.e online. Instead, we can compute and store the answers to all of them in any order and at the end return the stored results. This approach is called an offline processing of queries. More specifically, we are going to use MO's algorithm. The general idea is of this method is also explained here. We are going to divide array $A$ into bins of size $B$. We will pick the best suitable $B$ at the end of the analysis. Next, we are going to distribute queries to these bins in the following way: the first bin will contain queries with left end point in a range $[0, B  1]$, the second one, queries with left end point in a range $[B, 2 \cdot B  1]$ and so on. We are going to compute answer to queries in each bin independently of another bins, so for now, let's focus on answering queries from one bin, and remember that we will have to do it for all $\lceil N / B \rceil$ bins. Now we are about to answer queries from one bin. The first observation we can make, is that all these queries have left point not further away than B to other queries from the bin. This fact was the motivation of distributing queries to bins and we will use it later. First, we are going to sort queries in the bin by their right end point in ascending order, and process them one by one in this sorted order. Next, we will need a data structure which allows us to perform fast the following operations: insert, delete, find elements as long as finding predecessors and successors of elements. Any balanced binary search tree is perfect here, and if you are using C++, then std::set is a good choice. Let's call our data structure $S$. At the beginning, we are going to insert all elements from the range of the first query to $S$ and we will compute the answer for this query using the equation given in the statement. This takes $O(N \cdot \log N)$ time, because the range can have up to $N$ elements and inserting each one takes $O(N \cdot \log N)$, if we picked an appropriate implementation of $S$. The invariant here is that, $S$ contains all elements from the last processed query and that a variable ans contains the answer to the last processed query. We are going to update $S$, as long as ans, for the next query, based on the values from the previous one. How to do that? Well, let's consider any two adjacent queries in the sorted order $[L_i, R_i]$, $[L_j, R_j]$. We know that $R_j \geq R_i$ and that the absolute difference between $L_i$ and $L_j$ is not greater than $B$. Based on these two facts, we are going to insert to $S$ all the elements from a range $[R_{i + 1}, R_j]$ keeping the ans up to date after each insertion. Similarly, if $L_j < L_i$, we will insert to $S$ all elements from a range $[L_j, L_{i  1}]$. Otherwise, we will delete elements from a range $[L_i, L_{j  1}]$. Notice that we can perform both insertion and deletion keeping ans up to date. This is easy to do, because after an insertion, we place a new element in between two elements, so we need to subtract from the ans their square difference. In addition, since we inserted the new element, we need to add to ans the squared difference between its value and the value of its predecesor. We have to do the same for its successor too. Deletion is analogous. After all these updates, we have computed the answer to the current query, which is very good. The only remaining question is what is the time complexity of all these operations. Notice that, since all queries are ordered by their right end points in ascending order, we will perform at most $N$ insertions from the right side of queries for the whole bin! This is very nice, because is follows that the total cost of all insertions to right sides of queries for a single bin takes $O(N \cdot \log N)$ time. What about insertions and deletions from the left side of queries? Well, do you remember when we noticed that all these endpoint do not differ more that by $B$? Using this fact, we know that insertions and deletions from the left side of a query to update ans to the answer for the next query take $O(B \cdot \log N)$. In order to get the total time complexity, we just need to sum up achieved results for all bins. Insertions to all right sides in all bins takes then $O(N / B \cdot N \cdot \log N)$ and insertions/deletions to all left sides to all queries takes $O(M \cdot B \cdot \log N)$. It is easy to notice that picking $B = \sqrt N$ is the best choice here. Doing this, the total time complexity is $O(\sqrt N \cdot N \cdot \log N + \sqrt N \cdot M \cdot \log N)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 25 Oct '15, 10:58

My solution is exactly the same, but it got TLE for the 4th sub task. Were the time limits too strict? And if yes, where could the code have been optimized ? MySolution answered 25 Oct '15, 14:14
In both add and remove you're searching the map more than once. Search for the right element once (using upper_bound and a hint for insertion) you can reduce it to searching once for both operations.
(25 Oct '15, 14:47)
I also feel the time limits are strict.
My code gave TLE in C++4.3.2 but the same code got AC in C++4.9.2 and C++14.
(26 Oct '15, 15:26)

@pkacprzak https://www.codechef.com/viewsolution/8629325 my solution complexity is O(N.LogN) but still it is giving TLE for subtask 2 ... As mentioned above NlogN complexity will pass .. please help me !! answered 25 Oct '15, 19:04

Link to the solutions are saying 'Access Denied'. answered 25 Oct '15, 22:16

Correct me if I'm wrong, but with a segment tree and using merge sort, this can be done in O(nlogn +mlogn) time and O(n) space. answered 25 Oct '15, 23:58

when I used 1)all data typed as Long long and faster inp method(getchar_unlocked) got TLE 2)all data typed as int and no faster inp method(getchar_unlocked) got TLE 3)all data typed as int and faster inp method(getchar_unlocked) got AC. answered 28 Oct '15, 09:37

When B= sqrt(N) then I am getting TLE in Java whereas for B = 2*sqrt(N) its getting passed in 8.99 seconds. answered 29 Oct '15, 02:05

I am unable to view author and tester's solutions... getting XML error. Can anyone please provide the correct links/fix the existing links? answered 22 Jan '17, 11:28

Why link to the solutions are saying 'Access Denied'?