Имеется задачка (исходное условие)
Отрезок целочисленной прямой длины N разбит на единичные отрезки, которые пронумерованы от 1 до N.
Их объединяют в группы по следующим правилам:
- Несколько подряд идущих отрезков, ни один из которых не принадлежит ни одной из групп, могут быть объединены в группу.
- Любая ранее созданная группа может быть уничтожена, при этом входившие в нее отрезки больше не относятся ни к какой группе и могут впоследствии быть отнесены к другим группам.
Видно, что любой отрезок всегда находится не более, чем в одной группе.
Каждую группу можно идентифицировать парой чисел: номером первого и номером последнего отрезка, входящего в группу.
Первоначально нет ни одной группы.
Входные данные: Первая строка входных данных содержит число 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 - просто восстанавливает длины единичных отрезков, чтобы при поиске они вновь становились видимыми, что равносильно удалению их слияния.