Solution of CC

Let's denote:

• first[x] = the position of the first occurence of x
• second[x] = the position of the second occurence of x

The first observation we can make is that two cables a and b cross each other if and only if: first[a] < first[b] < second[a] < second[b] or first[b] < first[a] < second[b] < second[a]
In other words if we consider for each cable the interval [first[i], second[i]], then, we must count the number of pairs that intersect each other, but are not fully contained one in the other.

We can take advantage of the fact that these intervals are already sorted by their beginning.
We will proces each number from the input. Suppose we are at number i. If this is the first i we've encountered, then we will insert it in data structure. If it is the second one, then we need to query the data structure to get how many intervals are opened in the interval first[i], second[i], but close after second[i]. Because we process each point in sorted order, we can keep a segment tree or a similar DS that can provide add(pos, value) and getSum(x, y)