CSES Nested Ranges Count

Problems and Contests
#1

I am trying to solve this problem from CSES problem set and I’ve not been able to come up even with a half decent idea after spending around 2 hours on it.

I tried to google and read AC’ed solutions but can’t comprehend the approach taken.

Can someone just describe their approach?

#2

let a range be called (start, end)

if we sort the ranges by their start, we can find the number of ranges that contain x by querying the number of ranges y that satisfy y.start \leq x.start and y.end \geq x.end. This fits our situation because if we sort the ranges, then we guarantee that y.start \leq x.start must be true. Thus, we can use a DS like a Binary indexed tree to query the number of ranges that satisfy y.end >= x.end.

sort(all(a), [](range a, range b) {
    if (a.start == b.start) return a.end > b.end;
    return a.start < b.start;
});
for (range x : a) {
     count[x] = BIT.query(x.end, INF);
     BIT.add(x.end, 1);
}

counting the number of ranges that x contain is similar.

#3

Thanks a lot for replying.

What does the Binary Indexed Tree store in this case? IIRC, I can query a BIT to get sum of elements in a subarray defined by indexs i and j or update and element at index i, both these operation can be done in \mathcal{O(\log n)} using BIT.

The code that you provided what is BIT storing?

count[x] = BIT.query(x.end, INF)
#4

BIT stores the # of ranges

count[x] = BIT.query(x.end, INF) is querying the number of ranges before x that satisfy y.end>=x.end .

BIT.add(x.end, 1); increments that counter for x

2 Likes
#5

Thanks a lot. I got the gist of your approach finally but I ended up solving it using pbds ordered set(a slight modification to use it as ordered multiset)