PROBLEM LINK:
Author: amrmahmoud
Tester: dpraveen
Editorialist: tsreaper
DIFFICULTY:
MediumHard
PREREQUISITES:
BIT/Fenwick Tree, Geometry
PROBLEM:
Given N circles. No two circles touch or intersect each other. Given Q queries. Each query is a rectangle. Calculate the total area of the circles within the rectangle.
EXPLANATION:
Let ans(x_1,y_1,x_2,y_2) be the answer of the rectangle whose leftdown corner is (x_1,y_1) and rightup corner is (x_2,y_2), it’s obvious that:
ans(x_1,y_1,x_2,y_2)=ans(0,0,x_2,y_2)ans(0,0,x_1,y_2)ans(0,0,x_2,y_1)+ans(0,0,x_1,y_1)
So we can divide one query into four queries, now what we need to focus on is the total area of the circles within the rectangle whose leftdown corner is (0,0) and whose rightup corner is (x',y').
Let’s define the rightup point of a circle whose center is (x_0,y_0) and whose radius is r as (x_0+r,y_0+r). For each rectangle we need to calculate, there are 3 kinds of circles.

The rightup point of the circle is in the green rectangular area, so the whole circle is within the (0,0,x,y) rectangle. To solve this part of the problem, we need to sum up all the areas of the circle whose rightup point is in the green rectangular area. This is a classic two dimensional partial order problem which can be solved using BIT/Fenwick tree.

The rightup point of the circle is in the red rectangular area, so the straight line x=x' or y=y' goes through the circle and divide it into two halves. For a circle whose radius is r, there are at most 4r lines which go through the circle. For each line, we can precalculate which circles it goes through. Then for each query, we can use binary search to find the right most circle which x=x' goes through and whose rightup point is in the red rectangular area and sum up the areas. We can do the same thing for y=y'.

The rightup point of the circle is in the blue rectangular area. Note that no two circles touch or intersect each other, so for a fixed radius r, there are at most 2 circles whose rightup point is in the blue rectangular area. So we can loop through all r, and calculate the areas directly.
Sum all the three kinds of areas up, and we get the answer.
TIME COMPLEXITY:
For the first kind of circle, the time complexity is O((N+Q)logX), where X=50000.
For the second kind of circle, the time complexity is O(NR+XlogX+QlogX), where X=50000 and R=50.
For the third kind of circle, the time complexity is O(QR), where R=50.
MY SOLUTION:
(Sorry for the poor English.)