Hello, Codeforces!

Today I want to share with you something that often gets brushed off because it's a very basic concept — sorting. I think that this topic is often overlooked even though it can be very useful. This blog (my first on Codeforces, yaay) is thus rather intended for beginners in C++. I'll describe a technique that makes sorting fast to implement — lambdas. For simplicity, arrays will always mean vector in this blog.

There are two main usages of sorting I want to describe:

1. Sorting an auxiliary array to keep the original array unchanged.

This is often the case when our data is splitted into several separate arrays, connected together. For example, one array could contain a value of a cell and the other one — it's color. Say that we want to simultanously sort both those arrays by value (increasing).

In order to do that, we may rather introduce a new array, order, which will at first contain numbers from 0 to n - 1. We now simply sort according to the following lambda: sort(order.begin(), order.end(), [&values](int a, int b) { return values[a] < values[b]; });.

Let's break down the lambda expression. It countains three types of brakets:

a. square brakets containing captures — elements that are not parameters to the lambda but are captured for the use in the body of the lambda.

b. round brakets containing parameters — for sorting purposes those are always two elements of the same type as sorted vector elements (in case of vector<structs> you may also want to use references, ie. [](mystruct & a, mystruct &b)).

c. curly brackets containing body of our lambda — exactly the code that will execute and compute whether object a should go before b in sorted array. It should return bool value, that is true whenever we want to have a before b.

Now, when we have our array order sorted, it suffice to call colors[order[i]] and values[order[i]] to process the elements in the correct order.

1. We want to sort complex objects or we need more comparators than one.

Sometimes we need to sort objects that are more complex than basic integers / floats etc. Those use cases may include sorting weighted edges (ex. in Prim's MST algorithm), queries (which may later be required to reorder back to the original ordering), etc.

In those usecases we will rarely use captures and simply use relevant fields of sorted objects. Let's say, that our problem includes ranged queries, to which the answer is a single integer. Obviously, we need to answer queries in order of appearience in the testcase.

Let's also say that we discovered that processing those queries is very easy in the order of increasing length. We may then introduce a structure:

struct query {
    int left, right;
    int ans;
    int index;
};

During reading input we need to rememember to assign something like queries[i].index = i. Now we may solve our problem with the following code:

sort(queries.begin(), queries.end(), [](query& a, query& b) { return a.right - a.left < b.right - b.left; });
// ... process queries with your observation in order 0..n-1 and assign computed answer to queries[i].ans;
sort(queries.begin(), queries.end(), [](query& a, query& b) { return a.index < b.index; });
for(query& q : queries)  cout << q.ans << endl; 

Example usage of this technique is problem 1513C.