// tutoring dilemma
// using segment tree but pbds(policy based data structure) can also be used
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000000007
#define fo(i, l, r) for(i=l;l<r?i<r:i>r;l<r?i++:i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
ll segtree[2000008];
int update(int l, int r, int up_idx, int val, int idx) {
if(up_idx<l || up_idx>r) return segtree[idx];
if(l==r) return segtree[idx]=val;
int mid=l+(r-l)/2;
return segtree[idx]=update(l, mid, up_idx, val, idx*2)+update(mid+1, r, up_idx, val, idx*2+1);
}
ll fetch(int l, int r, int cl, int cr, int idx) {
if(cl>r || cr<l) return 0;
int mid=l+(r-l)/2;
if(cl<=l && r<=cr) return segtree[idx];
return fetch(l, mid, cl, cr, idx*2)+fetch(mid+1, r, cl, cr, idx*2+1);
}
int main() {
int n;cin >> n;
vector<vector<int>> v1,v2;
for(int i=0;i<n;i++) {
int a,b;cin >> a >> b;
v1.pb({a,b});
}
for(int i=0;i<n;i++) {
int a,b;cin >> a >> b;
v2.pb({a,b});
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
int freq[400008];
memset(segtree, 0, sizeof(segtree));
memset(freq, 0, sizeof(freq));
vector<int> tempv;
for(auto var:v1) tempv.pb(var[1]);
for(auto var:v2) tempv.pb(var[1]);
sort(tempv.begin(), tempv.end());
int i=0,j=0,count=1;
map<int,int> mp;
while(i<tempv.size()) {
int curr=tempv[i];
while(i<tempv.size() && tempv[i]==curr) i++;
mp[curr]=count;
count++;
}
ll ans=0;
i=0,j=0;
while(j<n) {
while(i<n && v1[i][0]<v2[j][0]) {
freq[mp[v1[i][1]]]++;
update(1, 2*n+1, mp[v1[i][1]], freq[mp[v1[i][1]]], 1);
i++;
}
if(mp[v2[j][1]]!=1) {
ans+=fetch(1, 2*n+1, 1, mp[v2[j][1]]-1, 1);
}
j++;
}
cout << ans << "\n";
return 0;
}
Could you please share the code of PBDS too or share the approach, for this question.