### PROBLEM LINK:

**Author:** Alei Reyes

**Tester:** Hasan Jaddouh

**Editorialist:** Praveen Dhinwa

### 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**

The underlying directed graph representing the friendship relation, will have a special structure. Firstly a person will have exactly one best friend, means that out degree of each vertex will be 1. However, it might be the case, there could be a lot of people who have a person as a best friend, meaning that in degree of a vertex could be larger than one, or could even be zero. These conditions ensure that graph will of formed of some lines and cycles which might contain some incoming lines. Please see the below image for some examples.

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.

- Both the vertices belong to cycle.
- One belongs to cycle and other to the line
- Both of them belong to the line.

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 vertices
- Number of edges
- Number of cycles

#### Number of vertices

It’s the easiest one. It will be equal to R - L + 1.

#### Number of edges

Let 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 pre-calculate 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 cycles

You 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.