PROBLEM LINK: Problem
Author and editorialist: Ildar Gainullin
Tester: Hasan Jaddouh
DIFFICULTY: Medium-Hard
PREREQUISITES: Convex Hull, Segment tree
EXPLANATION:
Both points from diameter are lying on convex hull
Expected number of points on convex hull when points are generated randomly from square K \cdot K is O(log K).
You can read the proof here: On the Expected Complexity of Random Convex Hulls.
Let’s build segment tree, each segment will contain convex hull of points from the segment.
So to answer the question, we will split query segment on the O(log n) segments from segment tree, and find convex hull using only points from these hulls.
With Andrew algorithm we can build new hull in O(log n \cdot log K), and then find diameter in O(log K) or O(log^2 K).
So, complexity of this algorithm is O((n + q) \cdot log K \cdot log N)