Мое решение.

Для понимания решения советую ознакомиться со структурой данных ordered_set из глубин C++, если вы ещё с ней не знакомы, она представляет из себя std::set с расширенными возможностями. https://codeforces.me/blog/entry/11080?locale=ru

Будем решать задачу оффлайн, с помощью сортировки событий(сканлайна). Каждый отрезок превратим в событие, состоящее из правой границы, длины отрезка и номера отрезка. Будем хранить для каждого отрезка по номеру его левую границу. Отсортируем события сначала по координате, потом по длине.

Для каждого отрезка $$$i$$$ я хочу найти такое количество отрезков, что их правая граница $$$\leq right_i$$$, а левая граница $$$\geq left_i$$$. Эти отрезки по определению вложены в наш. Для правой границы найти такие отрезки легко, просто будем перебирать их в порядке возрастания правой границы, но вот чтобы одновременно искать и количество таких левых, придётся потрудиться. Будем обходить события в этом отсортированном порядке и поддерживать ordered_set lefts, в котором будут храниться левые границы отрезков, которые на текущий момент закрылись(встретилась их правая граница), не включая текущий отрезок.

С помощью метода lefts.order_of_key({left[ind] — 1, n}) мы найдём количество элементов меньших left[ind](левой границы текущего отрезка), отняв это значение от lefts.size() мы получим количество левых границ >= left[ind]. После чего прибавим эту величину к ответу и добавим текущую левую границу в lefts.

Для чего мне сортировать по длине? Если у нас будут 2 отрезка 1 5 и 2 5, и если мы обработаем сначала 1 5, добавив его левую границу, то мы не учтём при подсчёте 2 5, так как его левая граница ещё не была добавлена. Если у отрезков одинаковая правая граница, то мы должны обрабатывать отрезки от меньшей длины к большей. Это работает, если отрезки различны, если могут быть одинаковые отрезки, то для одинаковых я бы решил случай отдельно

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;
///создаем ordered_set пар, так как нам придется хранить одинаковые числа, less_equal не работает:(
inline void fio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

inline void solve() {
    struct event{ ///в этой структуре мы храним событие в виде правой границы, длины отрезка и номера отрезка
        int x, len, ind;
        ///можно было бы хранить pair/tuple, которые бы сами сравнивались, но мне такой подход больше нравится

        event() {
        ;
        }

        event(int xx, int llen, int iind) {
            x = xx;
            len = llen; ///Длина нам нужна для сортировки, ведь если у нас будут 2 отрезка
            /// 1 5  2 5, и если мы обработаем сначала 1 5, добавив его левую границу, то мы не учтём при подсчёте 2 5, так как его левая граница ещё не была добавлена
            /// если у отрезков одинаковая правая граница, то мы должны обрабатывать отрезки от меньшей длине к большей
            ///это работает, если отрезки различны, если могут быть одинаковые отрезки, для них я бы решил случай отдельно
            ind = iind;
        }

        bool operator <(const event& b) { ///определяем operator <, чтобы sort работал
            if (x < b.x) return true;
            if (x > b.x) return false;
            return len < b.len;
        }

    };

    int n;

    cin >> n;
    vector<event> events;
    vector<int> left(n), ans(n, 0); ///левые границы нужно хранить, чтобы потом закидывать их в lefts, когда обработаем соответствующую правую границу

    for (int i = 0; i < n; ++i) {
        int r;
        cin >> left[i] >> r;
        events.emplace_back(r, r - left[i] + 1, i);
    }///Считываем данные и закидываем события

    sort(events.begin(), events.end());
    ordered_set lefts;
    for (const auto& [x, len, ind]: events) { ///идём по правым границам и закидываем в lefts их левые после обработки
        /*
        lefts.size() это количество отрезков, которые уже закончились(была их правая граница)
         в lefts мы кладём только такие, ведь закидываем их только встретив правую границу.
         Среди всех таких левых границ нам нужно выбрать только те, left которых >= left нашей текущей правой границы,
         которую мы обрабатываем.
         С помощью order_of_key найдём количество элементов меньших left[ind], после чего отнимем это количество от lefts.size()
         Получим количество вложенных отрезков.
       */
        ans[ind] = lefts.size() - lefts.order_of_key({left[ind] - 1, n});
        lefts.insert({left[ind], ind}); ///добавляем левую границу только после подсчёта ответа, чтобы не поссчитать самого себя
    }

    for (int t: ans) {
        cout << t << '\n';
    }
}
int main() {
    fio();
    solve();

    return 0;
}

Мне интересно, существует ли более простое решение данной задачи без использования продвинутых структур?

Вроде ДО(любой другой структуры rsq с обновлением), ДД(любого другого bst). ordered_set заменяет здесь продвинутую структуру, не хватает даже обычного set. Это самое простое, что мне удалось придумать с идейной точки зрения и реализации.

Хочется услышать ваши мысли по поводу решения этой задачи, возможно вы поможете мне отыскать более простое решение, или доказать, что его не существует.

Моё решение работает за $$$O(nlogn)$$$. Хочется более простое решение с такой же асимптотикой. Допустимы чуть большие вроде $$$O(nlog^2n)$$$

Почему мне это интересно и важно? Потому что в этой простой идее может скрываться какой-то классный идейный подход, который почему-то сейчас мне недоступен, и который позволит мне идейно развиться