AMR15E - Editorial

ma5termind · November 17, 2015, 3:15am

PROBLEM LINK

[Practice][1]
[Contest][2]

Panel Members

Problem Setter: [Suhash][3]
Problem Tester:
Editorialist: [Sunny Aggarwal][5]
Contest Admin:
Russian Translator:
Mandarin Translator:
Vietnamese Translator:
Language Verifier:

DIFFICULTY:

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

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.