Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 18 19 20 21 22 23 24 >> Отображать по:
#2786
Разрезание графа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:

  • cut — разрезать граф, то есть удалить из него ребро;
  • ask — проверить, лежат ли две вершины графа в одной компоненте связности.

Известно, что после выполнения всех операций типа cut рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа ask.

Входные данные

Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа \(n\), количество рёбер \(m\) и количество операций \(k\) (\(1 \le n \le 50\,000\), \(0 \le m \le 100\,000\), \(m \le k \le 150\,000\)).

Следующие \(m\) строк задают рёбра графа; \(i\)-ая из этих строк содержит два числа \(u_i\) и \(v_i\) (\(1 \le u_i, \, v_i \le n\)), разделённые пробелами — номера концов \(i\)-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.

Далее следуют \(k\) строк, описывающих операции. Операция типа cut задаётся строкой „cut \(u\) \(v\)“ (\(1 \le u, \, v \le n\)), которая означает, что из графа удаляют ребро между вершинами \(u\) и \(v\). Операция типа ask задаётся строкой „ask \(u\) \(v\)“ (\(1 \le u, \, v \le n\)), которая означает, что необходимо узнать, лежат ли в данный момент вершины \(u\) и \(v\) в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.

Выходные данные

Для каждой операции ask во входном файле выведите на отдельной строке слово „YES“, если две указанные вершины лежат в одной компоненте связности, и „NO“ в противном случае. Порядок ответов должен соответствовать порядку операций ask во входном файле.

Примеры
Входные данные
3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1
Выходные данные
YES
YES
NO
NO
#2787
LCA-Offline
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Изначально имеется дерево состоящее только из корня (вершина с номером \(1\)). Требуется научиться отвечать на следующие запросы:

  • ADD \(a\) \(b\) — подвесить вершину \(b\) за вершину \(a\) (гарантируется, что вершина \(a\) уже существует, а вершина \(b\) еще не существует).
  • GET \(a\) \(b\) — вернуть LCA вершин \(a\) и \(b\).

Все номера вершин от \(1\) до \(N\).

В каждый момент времени у нас есть одно дерево.

Входные данные

В первой строке входного файла содержится число \(k\) — количество запросов. Следующие \(k\) строк содержат сами запросы. Гарантируется, что число запросов каждого из типов не превосходит \(500\,000\).

Выходные данные

Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.

Примеры
Входные данные
9
ADD 1 2
ADD 1 3
ADD 2 4
GET 1 3
GET 2 3
GET 3 4
ADD 2 5
GET 4 5
GET 5 5
Выходные данные
1
1
1
2
5
#2789
Своппер
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

Современные компьютеры зацикливаются в десятки раз эффективнее человека
Рекламный проспект OS Vista-N

Перед возвращением в штаб-квартиру корпорации Аазу и Скиву пришлось заполнить на местной таможне декларацию о доходах за время визита. Получилась довольно внушительная последовательность чисел. Обработка этой последовательности заняла весьма долгое время.

— Своппер кривой, — со знанием дела сказал таможенник.

— А что такое своппер? — спросил любопытный Скив.

Ааз объяснил, что своппер — это структура данных, которая умеет делать следующее.

  • Взять отрезок чётной длины от \(x\) до \(y\) и поменять местами число \(x\) с \(x+1\), \(x+2\) с \(x+3\), и т.д.
  • Посчитать сумму чисел на произвольном отрезке от \(a\) до \(b\).

Учитывая, что обсчёт может затянуться надолго, корпорация «МИФ» попросила Вас решить проблему со своппером и промоделировать ЭТО эффективно.

Входные данные

Во входном файле заданы один или несколько тестов. В первой строке каждого теста записаны число \(N\) — длина последовательности и число \(M\) — число операций (\(1 \le N, \, M \le 100\,000\)). Во второй строке теста содержится \(N\) целых чисел, не превосходящих \(10^6\) по модулю — сама последовательность. Далее следуют \(M\) строк — запросы в формате 1 \(x_i\) \(y_i\) — запрос первого типа, и 2 \(a_i\) \(b_i\) — запрос второго типа. Сумма всех \(N\) и \(M\) по всему файлу не превосходит \(200\,000\). Файл завершается строкой из двух нулей. Гарантируется, что \(x_i \le y_i\), а \(a_i \le b_i\).

Выходные данные

Для каждого теста выведите ответы на запросы второго типа, как показано в примере. Разделяйте ответы на тесты пустой строкой.

Примеры
Входные данные
5 5
1 2 3 4 5
1 2 5
2 2 4
1 1 4
2 1 3
2 4 4
5 5
1 2 3 4 5
1 2 5
2 2 4
1 1 4
2 1 3
2 4 4
0 0
Выходные данные
Swapper 1:
10
9
2

Swapper 2:
10
9
2
#2790
Range Minimum Query
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

Компания Giggle открывает свой новый офис в Судиславле, и вы приглашены на собеседование. Ваша задача — решить поставленную задачу.

Вам нужно создать структуру данных, которая представляет из себя массив целых чисел. Изначально массив пуст. Вам нужно поддерживать две операции:

  • запрос: «? i j» — возвращает минимальный элемент между \(i\)-ым и \(j\)-м, включительно;
  • изменение: «+ i x» — добавить элемент \(x\) после \(i\)-го элемента списка. Если \(i = 0\), то элемент добавляется в начало массива.

Конечно, эта структура должна быть достаточно хорошей.

Входные данные

Первая строка входного файла содержит единственное целое число \(n\) — число операций над массивом (\(1 \le n \le 200\,000\)). Следующие \(n\) строк описывают сами операции. Все операции добавления являются корректными. Все числа, хранящиеся в массиве, по модулю не превосходят \(10^9\).

Выходные данные

Для каждой операции в отдельной строке выведите её результат.

Комментарий к примеру тестов.

Нижеследующая таблица показывает процесс изменения массива из примера.

ОперацияМассив после её выполнения
изначальнопуст
+ 0 55
+ 1 35, 3
+ 1 45, 4, 3
+ 0 22, 5, 4, 3
+ 4 12, 5, 4, 3, 1

Примеры
Входные данные
8
+ 0 5
+ 1 3
+ 1 4
? 1 2
+ 0 2
? 2 4
+ 4 1
? 3 5
Выходные данные
4
3
1
#2791
В начало строя!
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Капрал Питуца любит командовать своим отрядом. Его любимый приказ «в начало строя». Он выстраивает свой отряд в шеренгу и оглашает последовательность приказов. Каждая приказ имеет вид «Солдаты с \(l_i\) по \(r_i\) — в начало строя!»

Пронумеруем солдат в начальном положении с 1 до \(n\), слева направо. Приказ «Солдаты с \(l_i\) по \(r_i\) — в начало строя!» означает, что солдаты, стоящие с \(l_i\) по \(r_i\) включительно, перемещаются в начало строя, сохраняя относительный порядок.

Например, если в некоторый момент солдаты стоят в порядке \(2, 3, 6, 1, 5, 4\), после приказа: «Солдаты с \(2\) по \(4\) — в начало строя!» порядок будет \(3, 6, 1, 2, 5, 4\).

По данной последовательности приказов найти конечный порядок солдат в строю.

Входные данные

В первой строке два целых числа \(n\) and \(m\) (\(2 \le n \le 100\,000\), \(1 \le m \le 100\,000\)) — количество солдат и количество приказов. Следующие \(m\) строк содержат по два целых числа \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)).

Выходные данные

Выведите \(n\) целых чисел — порядок солдат в конечном положении после выполнения всех приказов.

Примеры
Входные данные
6 3
2 4
3 5
2 2
Выходные данные
1 4 5 2 3 6
Страница: << 18 19 20 21 22 23 24 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест