652D - Nested Segments - CodeForces Solution

#include<iostream>
#include<algorithm>
#include<cstring>
#include<functional>
#include<vector>
#include<queue>
#include<unordered_map>
#include<numeric>
using namespace std;

const int N = 200004;

struct interval {
    int l, r, i;
}e[N];
int x[N << 1];
int f[N << 1];
int ans[N];
int n;

int lb(int x) { return x & -x; }

void add(int x) {
    while(x <= n * 2) {
	f[x] += 1;
	x += lb(x);
    }
}

int query(int x) {
    int res = 0;
    while(x) {
	res += f[x];
	x -= lb(x);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(f, 0, sizeof(f));
    int l, r, y, i, j;
    cin >> n;
    j = 0;
    for(i = 0; i < n; i++) {
	cin >> e[i].l >> e[i].r;
	x[j++] = e[i].l;
	x[j++] = e[i].r;
	e[i].i = i;
    }
    sort(e, e + n, [&](auto p, auto q) { return p.r == q.r ? p.l > q.l : p.r < q.r; });
    sort(x, x + (n << 1));
    for(i = 0; i < n; i++) {
	y = upper_bound(x, x + n * 2, e[i].l) - x;
	ans[e[i].i] = query(n * 2) - query(y);
	add(y);
    }
    for(i = 0; i < n; i++) cout << ans[i] << '\n';
    return 0;
}