Hello Codeforces!
Today I wanted to gain contributions share my small invention during my upsolving. I don't know if there existed a similar idea yet, but as far as I can tell, the editorial for the problem does not use my idea. I think it would be nice to share with you guys and have your opinions on this idea.
Idea explanation
How do we build Merge-sort tree again?
Merge sort tree is a Segment tree, each node of whose contains a sorted set/vector of every element in its range. We build it in a bottom-up manner. To build the parent nodes, we merge 2 sets/vectors of the children the same as we do in the merge-sort algorithm in $$$O(n)$$$, hence the name Merge-sort tree.
But there is another way.
Let A
be the array we are building the merge-sort tree on, it[i]
be the vector that contains sorted elements in the range conquer by the i-th
node. Let's create another array B
that stores the following pairs: B[i].first = A[i], B[i].second = i
. We sort the array B
in the increasing order of first
. Then we iterate each pair element value, position
of B
in that sorted order, push the value
to the back of every it[i]
where i
is the node of the merge-sort tree that contains position
.
We can see that I sort the array before inserting, so I decided to call this trick sort before insert
. Do you guys have a better name?
Some advantages of "sort before insert" over the classical way
- We can handle the case where we have multiple element located in the same position.
- With efficient style we can build this tree iteratively.
Here is the small snippet for building the tree.
const int N = 1e5; // limit for array size
int n; // array size
vector<int> it[2 * N];
void build(const vector<int>& a) {
vector<pair<int, int>> b;
for (int i = 0; i < (int)a.size(); ++i) {
b.emplace_back(a[i], i);
}
sort(b.begin(), b.end());
for (auto [val, p]: b) {
for (p += (int)a.size(); p > 0; p >>= 1)
it[p].push_back(val);
}
}
So now we can call merge-sort tree — quick-sort tree from now :))
Can we do with ranges?
As we can see, each node in the merge-sort tree contains only elements of its range, and in the sort before insert
version, we used point-update to build the tree. Can we do the same with range-like update? Yes, yes we can with sort before insert
!
But what does each node contains exactly? We already know that for every interval, we can break it into $$$O(\log n)$$$ sub-intervals, each of them will correspond to a node of the segment tree. So if we have some intervals with some associated value, we can add these values to every node corresponding to the sub-interval of the considering interval, so that the vectors of the nodes will still be sorted.
Here is the implementation of the idea.
const int N = 1e5; // limit for array size
int n; // array size
vector<int> it[2 * N];
struct Range {
int l, r, value; // [l, r)
};
void build(vector<Range> a) {
sort(a.begin(), a.end(), [](const Range& u, const Range& v) { return u.value < v.value});
int n = (int)a.size();
for (auto [l, r, val]: b) {
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) it[l++].push_back(val);
if (r & 1) it[--r].push_back(val);
}
}
}