PROBLEM LINK:Author: Alei Reyes DIFFICULTY:medium hard PREREQUISITES:data structures, fenwick tree, segment tree, number of connected component, number of intervals inside an interval PROBLEM:There are total $n$ people. Each person has his best friend $a_i$. A person admires himself and all the people whom his best friend admires. A guild is defined as largest group of persons such that for any two people in the group, there is a person whom both admire. You are given few queries, in each query, you are given a range $[L, R]$, you have to answer total number of guilds when all the persons who are not in the range $[L, R]$ stop admiring their best friend's admirers (i.e. they now admire themselves only). Each query is independent of other query. EXPLANATION:Understand the structure of underlying friendship graph A guild in this graph will be composed of a connected component. You can notice that in a connected component, for every set of two vertices, there will be a vertex who is admired by both. You can see this easily in the line case. In case of cycle with incoming lines, you can verify it by taking these three cases.
So, the problems asks us to find number of connected components in the underlying graph. From the structure of the graph, you can notice that the number of connected components will be equal to number of vertices  number of edges + number of cycles. So, you have to maintain all these three parameters for answering each query.
Number of verticesIt's the easiest one. It will be equal to $R  L + 1$. Number of edgesLet us represent each edge by its endpoints by two variables, $from$ and $to$, denoting that the edge goes from vertex $from$ to vertex $to$. Let us first precalculate the intervals for the edges $[from, to]$, where for each index $i$, such that $from = i$, and $to = f_i$, where $f_i$ denotes the best friend of $i$th person. Finding number of edges in range $[L, R]$ is same as finding number of above defined intervals contained inside the range $[L, R]$. Note that if $f_i$ belongs outside the range, then it won't be counted. Number of cyclesYou can handle the cycles (with some incoming lines into it) in the similar way. Represent a cycle by two values, the smallest and the largest index of some vertex present in it. Finding number of intervals lying inside a given range.So, we want to number of integer $i, f_i$, such that $L \leq i, f_i \leq R$. Let us create an array of arrays, $vec[i]$, where $vec[i]$ stores the right end point of the intervals whose left end point is $i$. Now, you can build a segment tree over it, whose each node will contain sorted order of right endpoints e in the segment tree node. While answering a query, if the query contains the segment node completely, you can just find the number of elements $< R$, by a simple binary search. This method will give you a complexity of $\mathcal{O}({(log \, n)}^2)$ complexity per query. Tester's Solutions:
This question is marked "community wiki".
asked 21 Aug '16, 20:32

I solved it via a different approach, a few seconds after contest ended, using Mo's algorithm: We need to add/remove nodes during Mo's algorithm and update the number of connected components accordingly. Consider the best friend relationship as an edge from node i to best[i]. For each node, keep track of the number of edges to and from undeleted nodes. Say it is Count[i]. When deleting a node, we have 3 cases: Node insertion can be done similarly. So we can insert and delete nodes in $O(1)$ time. Total time complexity: $ N\sqrt{N} $ answered 22 Aug '16, 02:28

Counting points within any rectangle can be done offline  split the rectangle into four that contain the origin of the coordinate system (like with 2D prefix sums), sort them, add points sorted by one coordinate and use a Fenwick tree to count the number of added points within any range $[0,R]$. This has $O(Q\log)$ time complexity; in this case, just due to Fenwick trees, since the coordinates are already small. answered 22 Aug '16, 00:47

image provided is not visible . could u fix that? answered 23 Aug '16, 19:59

gvaibhav21, could you explain how you arrived at the total time complexity? I considered your approach but concluded it could TLE. How did you upperbound the total number of insertions/deletions you need to do? Also, how do you make sure you keep your the current number of connected components updated after each insertion/deletion in O(1)? Don't you need to assign labels to each node in affected connected components, thus making the worst case O(n)? answered 22 Aug '16, 06:08
2
I limited the number of insertions and deletions using Mo's algorithm: https://blog.anudeep2011.com/mosalgorithm/ We can insert/delete nodes in O(1) time, using the formula's involving Count[i] in the 3 different cases I have described in the answer. You don't need to explicitly maintain the connected components, just their number.
(22 Aug '16, 09:43)
