### Links

[Contest](https://www.codechef.com/INSO2018/problems/CNTNODE)**Author:** Adarsh Kumar

**Tester:** Samarth Joshi

**Editorialist:** Adarsh Kumar

### DIFFICULTY:

Medium### PREREQUISITES:

Segment tree, Dynamic Programming### EXPLANATION:

The maximum value of*k*can be

*2logn*. This can be proved intuitively.

For every node representing the range *(l,r)* we will store three arrays:

*pre[i]* - number of ranges *(l,p)* for which *cnt = i*;

*suf[i]* - number of ranges *(p,r)* for which *cnt = i*;

*ans[i]* - number of ranges *(p,q)* for which *cnt = i*;

```
where <i>(1 <= i <= k), (l <= p,q <= r)</i>
```

Then a post order traversal is done to calculate the above values for every node. For merging the child nodes of a parent node:

*pre[i][node] = pre[i]*

*suf[i][node] = suf[i][right]*

*ans[i+j][node] = sum(suf[i]*pre[j][right])*

The answer to the problem is *ans[i][1]*

Authorâ€™s Solution can be found here

Testerâ€™s Solution can be found here