4-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Задача C. Запросы на перестановке

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

У вас есть перестановка $p_1, \ldots, p_n$ и массив целых чисел $a_1, \ldots, a_n$, который изначально заполнен нулями. Вам нужно обработать $q$ запросов одного из трёх типов:

• $1 l r x$: для всех $l <= i <= r$, добавить $x$ к $a_{p_i}$.
• $2 l r$: вычислить и вывести $a_l + a_{l+1} + \cdots + a_r$.
• $3 a b$: поменять местами $p_a$ и $p_b$.

Формат входного файла

В первой строке записаны два целых числа $n$ и $q$ ($2 <= n, q <= 10^5$) — размер перестановки и количество запросов. Во второй строке записаны $n$ целых чисел $p_1, \ldots, p_n$ ($1 <= p_i <= n$, $p_i \neq p_j$ если $i \neq j$). Каждая из следующих $q$ строк содержат описания запросов Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса: $1 l r x$ ($1 <= l <= r <= n$, $1 <= x <= 10^5$) для запросов первого типа. $2 l r$ ($1 <= l <= r <= n$) для запросов второго типа. $3 a b$ ($1 <= a, b <= n$, $a \neq b$) для запросов третьего типа.

Формат выходного файла

Выведите ответы на все запросы второго типа, каждый ответ в отдельной строке.

Пример:

Вход

6 9
4 6 3 1 2 5
1 4 5 3
3 3 5
1 2 3 6
3 3 6
3 2 1
2 1 5
2 1 6
1 1 5 6
2 4 6

Ответ

12
18
24

( Parassat Kyzyrkanov )

Комментарий/решение

Для решения этой задачи можно использовать дерево отрезков. Каждый узел дерева будет содержать информацию о сумме элементов на соответствующем отрезке перестановки.

Для выполнения первого типа запросов нужно обновить значение элемента в соответствующем листе дерева отрезков.

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

Для выполнения третьего типа запросов нужно поменять значения соответствующих элементов в листах дерева отрезков местами.

Пример реализации на Python:

n, q = map(int, input().split())

a = list(map(int, input().split()))

# построение дерева отрезков

tree = [0] * (4 * n)

def build(v, tl, tr):

if tl == tr:

tree[v] = a[tl]

else:

tm = (tl + tr) // 2

build(2 * v, tl, tm)

build(2 * v + 1, tm + 1, tr)

tree[v] = tree[2 * v] + tree[2 * v + 1]

build(1, 0, n - 1)

# обработка запросов

for _ in range(q):

query = input().split()

if query[0] == '1':

l, r, x = map(int, query[1:])

l -= 1 # приведение к 0-индексации

r -= 1

# обновление значения в дереве отрезков

def update(v, tl, tr):

if tl == tr:

tree[v] += x

else:

tm = (tl + tr) // 2

if l <= tm:

update(2 * v, tl, tm)

if r > tm:

update(2 * v + 1, tm + 1, tr)

tree[v] = tree[2 * v] + tree[2 * v + 1]

update(1, 0, n - 1)

elif query[0] == '2':

l, r = map(int, query[1:])

l -= 1 # приведение к 0-индексации

r -= 1

# нахождение суммы на отрезке в дереве отрезков

def query_sum(v, tl, tr):

if l > tr or r < tl:

return 0

if l <= tl and r >= tr:

return tree[v]

tm = (tl + tr) // 2

return query_sum(2 * v, tl, tm) + query_sum(2 * v + 1, tm + 1, tr)

print(query_sum(1, 0, n - 1))

else: # query[0] == '3'

l, r = map(int, query[1:])

l -= 1 # приведение к 0-индексации

r -= 1

# обмен значения

#include <iostream>

#include <vector>

using namespace std;

const int N = 1e5 + 5;

int n, q;

int a[N];

vector<int> tree(4 * N);

void build(int v, int tl, int tr) {

if (tl == tr) {

tree[v] = a[tl];

} else {

int tm = (tl + tr) / 2;

build(2 * v, tl, tm);

build(2 * v + 1, tm + 1, tr);

tree[v] = tree[2 * v] + tree[2 * v + 1];

}

}

void update(int v, int tl, int tr, int l, int r, int x) {

if (l > r) return;

if (tl == l && tr == r) {

tree[v] += x;

} else {

int tm = (tl + tr) / 2;

update(2 * v, tl, tm, l, min(r, tm), x);

update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, x);

tree[v] = tree[2 * v] + tree[2 * v + 1];

}

}

int query_sum(int v, int tl, int tr, int l, int r) {

if (l > r) return 0;

if (tl == l && tr == r) {

return tree[v];

} else {

int tm = (tl + tr) / 2;

return query_sum(2 * v, tl, tm, l, min(r, tm)) + query_sum(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);

}

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

cin >> n >> q;

for (int i = 0; i < n; i++) {

cin >> a[i];

}

build(1, 0, n - 1);

while (q--) {

int t;

cin >> t;

if (t == 1) {

int l, r, x;

cin >> l >> r >> x;

update(1, 0, n - 1, l - 1, r - 1, x);

} else if (t == 2) {

int l, r;

cin >> l >> r;

cout << query_sum(1, 0, n - 1, l - 1, r - 1) << '\n';

} else {

int l, r;

cin >> l >> r;

swap(a[l - 1], a[r - 1]);

build(1, 0, n - 1);

}

}

return 0;

}