PROBLEM LINKPanel MembersProblem Setter: Suhash DIFFICULTY:MediumHard PREREQUISITES:Offline processing, Mo's Algorithm, Binary Indexed Tree, Segment Tree, Mathematics. PROBLEM:Given an array consisting of $N$ elements each having value $A_i <= 10^9$. We are asked to process $M$ queries on array $A$ where each query consists of two integers $L$ and $R$ indicating a sub segment and asked to compute following expression on the given segment. $$Required Answer = \sum_{\substack{S_i \in S}}{S_i * i}$$ Where $S$ denotes the sorted list of unique elements in the range $L$ to $R$ and $i$ denotes the index of $S_i^{th}$ element in list $S$. ( 1 based indexing is used ) EXPLANATIONGiven problem has offline solution i.e we will store all the queries at first and will answer them all together in the end. Sort all the queries using Mo's algorithm. If you are not familiar with the Mo's Algorithm. Please go through this blog or this blog first. For the purpose of simplicity, Apply coordinate compression on the values of given array $A$ i.e map them in the range $[1, N]$ and also maintain a mapping of new values with the old values. Look at the following code for better understanding of mapping. void solve() { int n; cin >> n; map<int, int=""> M; // stl map for(int i=1; i<=n; i++) { cin >> A[i]; M[A[i]] = 0; } int newval = 0; for(auto &it: M) { it.sd = ++ newval; // assigning new value and maintaining mapping } } // note that M[x] stores the new value of element x. We are required to maintain following data structures to solve this problem efficiently.
Initially ans is initialised to 0. We will consider all queries one by one in new order and update the current $ans$ for the new query. Only $Add$ and $Remove$ function used in Mo's algorithm is important here. We will be looking at both one by one. ADD Function: Lets see what will happen when we add an element ( say $x$ ) to the current query to answer new query. Case 1: Either the added element $x$ already exist in the previous query. If Yes, then we don't need to worry about anything as it won't affect our answer but we will update our frequency array $F[]$ by incrementing count at index $x$ ( note that $x$ is new mapped value of original element and therefore it is in the range $[1, N]$ and we cam simply store frequency by keeping an array of size $N$ ). Case 2: Or the added element $x$ is not present in the range then we need to update the current answer but how ? Assume that $1$, $4$, $5$, $7$, $10$ are the $5$ elements that were present in the last query and we have a new element say $x = 6$ in the current query added to it. We can say that previous answer was $1 * 1 + 2 * 4 + 3 * 5 + 4 * 7 + 5 * 10$. and new answer will be $1 * 1 + 2 * 4 + 3 * 5 + 4 * 6 + 5 * 7 + 6 * 10$. We can generalise this change as follows: new answer = previous answer + ( number of element $ \lt x$ in the previous query + 1 ) * x + ( sum of all elements $\gt x$ in the previous query ) To find the number of elements $\lt x$, we have maintained a count Binary Indexed Tree $C$ and to find the sum of elements having value $\gt x$, we have maintained a sum Binary Indexed Tree $S$. Above idea can be better understood with the help of following code: void add(int position) { F[M[A[position]]] ++; if( F[M[A[position]]] == 1 ) { cbit>Update(M[A[position]], 1); sbit>Update(M[A[position]], A[position]); ans += cbit>RangeQuery(1, M[A[position]]) * A[position]; ans += sbit>RangeQuery(M[A[position]]+1, n); } } Remove Function Remove function is analogous to our add function but is exactly opposite. Please have a look at following function to understand it. void remove(int position) { F[M[A[position]]] ; if( F[M[A[position]]] == 0 ) { ans = cbit>RangeQuery(1, M[A[position]]) * A[position]; cbit>Update(M[A[position]], 1); sbit>Update(M[A[position]], A[position]); ans = sbit>RangeQuery(M[A[position]]+1, n); } } Please refer editorialist's solution for implementation detail and to understand above solution better. SIMILIAR PROBLEMSCOMPLEXITY$O(T*(N+M)*\sqrt(N)\log(N))$
This question is marked "community wiki".
asked 17 Nov '15, 03:15

This problem is currently not visible in practice. Can this please be made visible? @admin @ma5termind
please make this problem available for practice .