 # Help Needed with Nested Range Count , CSES

the link to the problem is this.
I have tried using fenwick tree .
my logic was as follows :
1 ) used coordinate compression on the ranges
2 ) made a vector of the type {{left,type = 0},{right,index}} , {{right,type = 1},{left,index}}
3 ) type == 0 means starting a range
4 ) type == 1 means range is over
5) sort the vector
6 ) while traversing the vector :
a) if type is 0 , we are starting the range , to know how many ranges contain
this range we need to know how many right index are present such that their
range is started and are >= then the right index of this range. I have used fenwick
tree for this purpose .After i get the answer i update the fenwick tree1 by increasing
the count of the right index .
b ) if type is 1 , we know the range is finished , to know how many ranges are within
this range , we need to check how many left index are present such that its range
is finished and it is >= left index of this range. I have used fenwick tree2 for this
purpose . After getting the answer we update the fenwick tree2 by increasing the
count of the left index .
the link to my solution is here
I am getting tle on one case .
Can anyone suggest some approach to this problem .

My Solution using policy based data structures, your approach is correct I also implemented the same idea using pbds.

AC_CODE
``````#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std ;
#define ar array
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
signed main(){
int n ;  cin >> n ;
oset<ar<int,2>>b,c;
vector<ar<int,3>>a(n) ;
vector<int>A(n),B(n)  ;
for(int i=0;i<n;i++)
cin >> a[i] >> a[i],a[i]=i ;

sort(a.begin(),a.end(),[&](const ar<int,3> i,const ar<int,3>j){
return ((i<j)||(i==j&&i>j)) ;
}) ;
for(int i=0,j=n-1;i<n;i++,j--){
A[a[i]]=i-b.order_of_key({a[i],-1}) ;
B[a[j]]=c.order_of_key({a[j]+1,-1}) ;
b.insert({a[i],i}) ;c.insert({a[j],i}) ;
}
for(int i=0;i<n;i++)
cout << B[i] <<' ' ;
cout << '\n' ;
for(int i=0;i<n;i++)
cout <<  A[i]<< ' ' ;
}
``````

PS: The links you gave in the post are swapped

6 Likes

Your AC_CODE just change map to unordered map

2 Likes

Thanks a lot !!

2 Likes

You can check this out for a clear video explanation if that helps:

2 Likes