Data structure to hold and retrieve points in a plane
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' &lt; x$ and $y' &gt; y$.
Point $(x',y')$ is in $B$ if $x' &gt; x$ and $y' &gt; y$.
Point $(x',y')$ is in $C$ if $x' &lt; x$ and $y' &lt; y$.
Point $(x',y')$ is in $D$ if $x' &gt; x$ and $y' &lt; 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' &gt; 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).