Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Двоичное дерево поиска

Условие задачи  
ID 38133
Организация коров фермера Джона
Темы: Двоичное дерево поиска   

Организация коров фермера Джона (UCFJ) направляет делегацию на Международную олимпиаду по овцеводству (IOI).
N  коров участвуют в выборе делегации (1≤N≤2⋅105). Они стоят в ряд, и корова i имеет породу bi.

Делегация состоит из непрерывного интервала как минимум двух коров - то есть из коров l…r для целых l и r удовлетворяющих 1≤l<r≤N. две внешние коровы выбранного интервала называются "лидерами". Чтобы избежать конфликта между породами коров каждый лидер должен иметь породу отличающуюся от остальных коров делегации (лидеров и не лидеров).

Определите количество способов выбрать делегацию.


Входные данные: 
Первая строка содержит N.
Вторая строка содержит N целых чисел b1,b2,…,bN, каждое в интервале [1,N].

Выходные данные: 
Количество возможных делегаций, на отдельной строке.

Примеры
Входные данные Выходные данные Пояснение
1 7
1 2 3 4 3 2 5
13 Каждая делегация соответствует одной из следующих пар лидеров:
(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).

 

ID 38476
Коллайдер
Темы: Двоичное дерево поиска    Задачи на моделирование   

Физики проводят эксперимент для исследования частиц трёх типов: x, y и z. Они запускают в коллайдер пронумерованный ряд из n частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с i-ого места ряда и моментально появляется на месте j. После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте k. Напишите программу, которая поможет физикам.

Входные данные
В первой строке файла два целых числа: n – количество частиц и m — общее количество воздействий и вопросов (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). Во второй строке — последовательность из символов x, y и z длиной n. На каждой из следующих m строк (1 ≤ m ≤ 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом a и после пробела дается два целых числа из интервала [1; n]. Первое из них показывает начальное, а второе  - конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом q и после пробела дается одно целое число из интервала [1; n]. Оно указывает позицию, которая интересует физиков.

Выходные данные
Выведите столько строк, сколько вопросов во входном файле. В строке номер i надо записать ответ на вопрос i — название соответствующей частицы x, y или z.

Пояснения к примеру
Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,
 

Примеры
Входные данные Выходные данные
1 15 6
xzxyyzxxzxyyzyx
a 2 10
a 15 4
q 3
a 12 2
q 14
q 2
y
z
y