Олимпиадный тренинг

Задача . G. Может ли Баш выйти из положения?


Задача

Темы: графы Деревья разделяй и властвуй Структуры данных *3400

Вау! Вы отлично помогли команде Р поймать всех покемонов, посланных Башем. Мяут, член частью команды Р, уже выучил человеческий язык, и теперь хочет обучиться программированию. Он согласился освободить покемонов, если Баш ответит на его вопросы.

В начале Мяут дает Башу взвешенное дерево из n вершин и последовательность a1, a2..., an, которая является перестановкой чисел 1, 2, ..., n. Теперь Мяут задает q запросов в одной из следующих форм:

  • 1 l r v значит, что Баш должен посчитать , где dist(a, b) — длина кратчайшего пути от вершины a до вершины b в данном дереве.
  • 2 x значит, что Баш должен поменять местами ax и ax + 1 в заданной последовательности. Новая последовательность будет использоваться для следующих запросов.

Помогите Башу ответит на запросы!

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

Первая строка содержит два целых числа n и q (1 ≤ n ≤ 2·105, 1 ≤ q ≤ 2·105) — количество вершин в дереве и число запросов, соответственно.

Следующая строка содержит n целых чисел — последовательность a1, a2, ..., an, являющуюся перестановкой чисел 1, 2, ..., n.

Каждая из следующих n - 1 строк содержит три целых числа u, v, и w, означающих, что существует ребро между вершинами u и v длины w, (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 106). Гарантируется, что заданный граф является деревом.

Далее следуют запросы. Каждый запрос записан в двух строках. В первой строке находится целое число t, обозначающее тип запроса. Следующая строка содержит описание запроса:

  • t = 1: Вторая строка содержит три числа a, b и c (1 ≤ a, b, c < 230), используя которые, l, r и v могут быть получены по следующей формуле:
    • ,
    • ,
    • .
  • t = 2: Вторая строка содержит целое число a (1 ≤ a < 230), используя которое, x может быть получено по следующей формуле:
    • .

Число ansi равно ответу на i-й запрос, можете считать, что ans0 = 0. Если i-й запрос имеет тип 2, то ansi = ansi - 1. Гарантируется, что:

  • для каждого запроса типа 1: 1 ≤ l ≤ r ≤ n, 1 ≤ v ≤ n,
  • для каждого запроса типа 2: 1 ≤ x ≤ n - 1.

Операция означает побитовое исключающее ИЛИ.

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

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

Примечание

В примере запросы следующие:

  • 1 1 5 4
  • 1 1 3 3
  • 2 3
  • 2 2
  • 1 1 3 3

Примеры
№Входные данныеВыходные данные
1 5 5
4 5 1 3 2
4 2 4
1 3 9
4 1 4
4 5 2
1
1 5 4
1
22 20 20
2
38
2
39
1
36 38 38 
23
37
28

time 5000 ms
memory 768 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет