Have you submitted the solution? The Time Limit is 15s, so try to submit it.

If the queries are of type [i..j] you can try using Mo's Algorithm to sort the queries: here

This allows solving the Q queries with O(N sqrt(N)) insertions / deletions of points.

Now, you have to think of a Data Structure that should be able to insert points, delete points, and query how many points are within Manhattan distance <= d. I believe you could use a QuadTree for that matter, and just keep the required number dynamically at each step.

For example:

When inserting a point, first query how many points are within Manhattan distance <= d from that point (which can be done using a QuadTree or KD-Tree -> see if a whole region intersects with the needed square, if it is completely within the square then just add all the points in the region -- QuadTrees should help you do that, if not recurse), and add this number to TOTAL. When deleting a point, query the same thing and then subtract from TOTAL (excluding the point itself, of course). I believe 2d range trees have a complexity of O(sqrt(N)), although I am not very sure. Total complexity should be O(N*Q), although in practice it should go better :).

If you do not understand what square I am reffering to, here is a drawing: