Деревья отрезков. Непересекающиеся отрезки

Имеется задачка (исходное условие)

Отрезок целочисленной прямой длины N разбит на единичные отрезки, которые пронумерованы от 1 до N.

Их объединяют в группы по следующим правилам:

1. Несколько подряд идущих отрезков, ни один из которых не принадлежит ни одной из групп, могут быть объединены в группу.
2. Любая ранее созданная группа может быть уничтожена, при этом входившие в нее отрезки больше не относятся ни к какой группе и могут впоследствии быть отнесены к другим группам.

Видно, что любой отрезок всегда находится не более, чем в одной группе.

Каждую группу можно идентифицировать парой чисел: номером первого и номером последнего отрезка, входящего в группу.

Первоначально нет ни одной группы.

Входные данные: Первая строка входных данных содержит число N – количество отрезков и число K – количество запросов (1 ≤ N, K ≤10^5). Далее идет K строчек, содержащих запросы к структуре данных. Каждый запрос начинается с числа 1 (запрос на создание группы) или 2 (запрос на удаление группы). После числа 1 указывается два других числа l и r (1 ≤ l ≤ r ≤ N), после числа 2 указывается одно число i (1 ≤ i ≤ N).

Выходные данные: Для каждого запроса типа 1 необходимо отрезки с номерами от l до r объединить в группу. Если все эти отрезки не входят ни в одну группу, запрос считается удачным и программа должна вывести 1. Если хотя бы один из этих отрезков уже относится к какой-то группе, запрос считается неудачным, объединение не производится и программа выводит 0.

Для каждого запроса типа 2 необходимо удалить группу, в которую входит отрезок с номером i, при этом программа должна вывести два числа: номер первого и последнего отрезка, входящих в удаляемую группу. Если отрезок с номером i не относится ни к одной группе, программа должна вывести два нуля.

она решается с помощью дерева отрезков. Я знаю как устроенна эта структура данных и могу применять её для поиска min/max, суммы и т.д. на отрезках, но не могу понять, как её применить к конкретно этой задаче.

Подскажите, как можно адаптировать стандартный RMQ/RSQ под эту задачу.

Вот например решение задачи о максимальном элементе на отрезке с помощью деревьев отрезков (RMQ):

#include <iostream>
using namespace std;
#include <algorithm> 
int t[4 * 100000];
int a[100000];
#define INF 100000007
void build(int v, int vl, int vr, int a[]) {
    if (vl == vr) {
        t[v] = a[vl]; 
        return;
    }
    int vm = vl + (vr - vl) / 2;
    build(2 * v + 1, vl, vm, a);
    build(2 * v + 2, vm + 1, vr, a);
    t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}

int query(int v, int vl, int vr, int l, int r) {
    if (r < vl || vr < l)
        return 0;
    if (l <= vl && vr <= r)
        return t[v];
    int vm = vl + (vr - vl) / 2;
    int ql = query(2 * v + 1, vl, vm, l, r);
    int qr = query(2 * v + 2, vm + 1, vr, l, r);
    return max(ql, qr);
}

int main()
{
    int N,Q,l,r;
    cin >> N; 
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    build(0,0,N-1,a);
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> l >> r;
        int p = query(0, 0, N - 1, l - 1, r - 1);

        cout << p << "\n";
    }
}

Зача решаеться такой же структурой данных, как в выше указанном примере

Вот здесь расписано всё про дерево отрезков.

P.S. Написал на питоне, но решение почти не рабочее. (7 баллов из 100)

def build(v, vl, vr):
    if vl == vr:
        t[v] = [1,[a[vl]]]
        return
    vm = vl + (vr - vl) // 2 
    build(2 * v + 1, vl, vm)
    build(2 * v + 2, vm + 1, vr)
    t[v] = [2,[vl,vr]]

def find(v, vl, vr, e):
    #print(v,vl,vr,e)
    if vl==vr:
        return v
    vm = vl + (vr - vl) // 2
    if t[2*v+2][0] and t[2*v+1][0]:
        if t[2*v+2][1][0]<=e:
            return find(2*v+2,vm+1,vr,e) 
        else:
            return find(2*v+1,vl,vm,e)
    else:
        return v

def remove(v, vl, vr, e):
    e = find(v, vl, vr, e)
    if t[e][0]==1:
        return [0,0]
    t[2*e+1][0]=1
    t[2*e+2][0]=1
    return [t[e][1][0]+1, t[e][1][1]+1]

def merge(v, vl, vr, e1, e2):
    e1 = find(v, vl, vr, e1)
    e2 = find(v, vl, vr, e2)
    if t[e1][0]==1 and t[e2][0]==1:
        t[e1][0]=0
        t[e2][0]=0
        return 1
    return 0

N,K = [int(i) for i in input().split()]
a = list(range(N)) 
t = [[0,[]] for i in range(4*N)]
build(0,0,N-1)

for i in range(K):
    q = [int(i) for i in input().split()]
    if q[0]==1:
        print(merge(0, 0, N-1, q[1]-1, q[2]-1))
    else:
        r = remove(0, 0, N-1, q[1]-1)
        print(r[0],r[1])

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

Функция find - обычный поиск по бинарному дереву за log, который не учитывает отрезки длиной меньше 1, merge - просто проверяет длины отрезков и если они оба равны 1, то приравнивает длины к 0 => функция find будет останавливаться на их предке, а предок и будет являться их слиянием. Ну и функция remove - просто восстанавливает длины единичных отрезков, чтобы при поиске они вновь становились видимыми, что равносильно удалению их слияния.