9

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

Отрезок целочисленной прямой длины 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 - просто восстанавливает длины единичных отрезков, чтобы при поиске они вновь становились видимыми, что равносильно удалению их слияния.

введите сюда описание изображения

4
  • Как мне кажется, то достаточно хранить множество пар начала и концов групп. А компаратор проверят пересечение этих пар по правилу: достаточно, что если координата(начало или конец) одной из группы принадлежит диапазону из координат другой группы. Но если вам нельзя использовать stl алгоритмы (Хотя вы подключили заголовок), то это решение не подходит :) 18 фев 2020 в 6:57
  • Хотелось бы узнать как эта задача решается именно деревом отрезков, так как это позволит находить ответ быстрее линейного времени.
    – faf0be
    18 фев 2020 в 7:23
  • STL использовать можно
    – faf0be
    18 фев 2020 в 7:23
  • У меня эта задача на 70, как на 100 хз
    – markussie
    18 фев 2020 в 14:04

2 ответа 2

2

Действительно можно использовать почти обычное дерево отрезков.

Для решения задачи ваше дерево должно уметь:

  1. Проверять, что все элементы (будем так называть единичные отрезки) на заданном отрезке [L, R] не принадлежат ни одному отрезку.
  2. Объединять все элементы на отрезке [L, R] в один отрезок или удалять их из него = красить их в цвет нового отрезка или в "белый".
  3. Находить, в цвет какого отрезка сейчас покрашен элемент i.

Для этого создадим массив пар, который будет хранить границы отрезка с цветом-индексом.

Далее нужно реализовать ДО, поддерживающее вышеописанные операции. Можно заметить, что если ДО поддерживает операции суммы на отрезке и присваивания на отрезке, то все три операции легко реализовать:

  1. "Самостоятельные" неокрашенные элементы будут изначально иметь цвет 0, а значит если все элементы от L до R неокрашенные, то сумма их цветов также равна нулю.
  2. Окрасим в 0 при разрушении или в цвет номера запроса при объединении.
  3. Сумма цветов от i до i.

Конкретную реализацию такого дерева можно найти, если немного погуглить (скорее всего, придется самостоятельно объединить два вида деревьев [прибавление-отрезок:сумма-отрезок] и [присвоение-отрезок:запрос-элемент]).

0

Кажется, есть проблема в терминологии. В этой задаче требуется настоящее дерево отрезков - segment tree, interval tree, которое действительно содержит именно отрезки/интервалы в упорядоченном виде, и имеет операции для добавления, удаления, объединения, проверки пересечения интервалов, поиск интервала, которому принадлежит точка. Имея такое дерево, решить данную задачу будет нетрудно.

А то, что процитировано - олимпиадники так называют структуру данных, которая позволяет быстро проводить некие операции над целым интервалом. Здесь она кажется ни к чему.

Убогое описание Segment Tree в англ. вики

А вот связанная с ней статья в русской вики относится как раз ко второй структуре

1
  • Я попробовал реализовать алгоритм на основе "настоящего" дерева отрезков, с хранением левой и правой границы отрезка (код и пояснение добавил в пост). Подскажите где я ошибаюсь.
    – faf0be
    19 фев 2020 в 10:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.