×

# Panel Members

Problem Setter: Suhash
Problem Tester:
Editorialist: Sunny Aggarwal
Russian Translator:
Mandarin Translator:
Vietnamese Translator:
Language Verifier:

Medium-Hard

# 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 )

# EXPLANATION

Given 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.

• An array say $F[]$ that stores the frequency of each element present in the considered range.
• A Segment tree / Binary Indexed Tree for the fast update and query sum say $S$.
• A Segment tree / Binary Indexed Tree for the fast update and query count say $C$.
• Let us assume that variable $ans$ denotes the answer of current query.

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.

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 PROBLEMS

Estimating Progress

Chef and Problems

Chef and Graph Queries

Tree and Queries

Sherlock and Inversions

# COMPLEXITY

$O(T*(N+M)*\sqrt(N)\log(N))$

This question is marked "community wiki".

1.7k11730
accept rate: 11%

19.8k350498541

3

(03 Sep '16, 00:26) 6★
2

please make this problem available for practice .

(07 Sep '16, 15:34)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,768
×1,302
×1,220
×52
×39
×4

question asked: 17 Nov '15, 03:15

question was seen: 2,470 times

last updated: 07 Sep '16, 15:35