Data structure to hold and retrieve points in a plane

Definition 1: Point $(x,y)$ is controlling point $(x',y')$ if and only if $x

-
$\mathrm{Remove}(x,y)$ - Removes a point $(x,y)$ from the system in $\mathcal{O}(\log n)$ complexity where $n$ is the number of points in the system.

-
$\mathrm{Score}(x,y)$ - Returns the number of points $(x,y)$ controls - number of points that $(x,y)$ is controlled by. Worst case complexity $\mathcal{O}(\log n)$ .

I've tried to solve it using multiple AVL trees, but could not come up with elegant enough solution.

This question appeared on my exams few days ago. The question should have relatively straightforward as it was worth $15/100$ points.
I tried to solve this by several AVL trees but couldn't come up with elegant enough solution.

Hints are welcome.

Solution outline:

We will maintain two AVL trees.

• Tree_X: will hold points sorted by their X coordinate.

• Tree_Y: will hold points sorted by their Y coordinate.

Each node within both trees will hold the following additional data:

• Number of leaves in left sub-tree.

• Number of leaves in right sub-tree.

For a point $(x,y)$ we will define regions $A$ ,$B$, $C$, $D$:

• Point $(x',y')$ is in $A$ if $x' y$.

• Point $(x',y')$ is in $B$ if $x' > x$ and $y' > y$.

• Point $(x',y')$ is in $C$ if $x'

• Point $(x',y')$ is in $D$ if $x' > x$ and $y'

Now it is clear that Score(x,y) = |C|-|B|.
However $|A|+|C|$, $|B|+|D|$, $|A|+|B|$, $|C|+|D|$ could be easily retrieved from our two AVL trees, as we will soon see.
And notice that $\frac {(|A| + |C| + |C| + |D|) - (|A| + |B| + |B| + |D|)}{2} = |C|-|B|$

Implementation of required operations:

-
Add(x,y) - We will add point (x,y) to both of our AVL trees. Since the additional data we are storing is affected only on the insertion path and since the insertion occurs in (logn), the total cost of Add(x,y) is O(logn).

-
Remove(x,y) - We will remove point (x,y) from both of our AVL trees. Since the additional data we are storing is affected only on the removal path and since the removal occurs in (logn), the total cost of Remove(x,y) is O(logn).

-
Score(x,y) - I will show how to calculate $|B|+|D|$ as others done in similar way and same complexity costs. It is clear that $|B|+|D|$ is the number of points which satisfy $x' > x$. To calculate this number we will:

• Find x in AVL_X. Complexity O(logn).

• Go upwards in Tree_X until the root and on each turn right we will sum the number of elements in left sub-tree of the son. Complexity O(logn).

Total cost of Remove(x,y) is O(logn).

StackExchange Computer Science Q#39558, answer score: 2