I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq i\leq n$ I would like to compute $|\lbrace j|j>i\wedge a_j > a_i\rbrace|$.
My idea: Implement an AVL tree, put elements from this sequence to this AVL tree from the last one to the first one. Before putting each element obtain the amount of larger elements the tree already contains. I can implement an AVL tree that would allow such operations.
But alas, I do have to implement such an AVL tree, since unfortunately the standard C++
std::set doesn't allow obtaining the distance between two iterators in logarithmic time.
Now I need this to solve a task from one of the former exams on algorithms and data structures. These exams usually contain two tasks, a "simpler" one and a "harder" one. And this is the "simpler" one. Now I doubt that a "simpler" task would require implementing an AVL tree. A "harder" task might; but a "simpler" one, doubtfully. Therefore, I would say, there should be a less laborious way to solve this task.
Is there any simpler way to compute what I need to compute?