Codeforces дерево отрезков задачи

Нексколько примеров (с решениями) задач на дерево отрезков

Автор WasylF, 9 лет назад ,

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

1. Дима и массив

Мама подарила мальчику Диме массив длины n. Массив этот не простой, а особенный. Дима может выбрать два числа i и d (1 ≤ i ≤ n, -1000 ≤ d ≤ 1000), и элемент с индексом i магически становится равным d. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от f до t? Дима легко справился с этими вопросами, сможете ли Вы?

Технические условия

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

В первой строке находятся два целых числа n и q (1 ≤ n ≤ 5•105, 1 ≤ q ≤ 105) — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a1, a2, . an (−1000 ≤ ai ≤ 1000) — начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть = или ?. Если строка начинается с =, то это операция присваивания. Далее следуют i и d, ограничения на которые описаны в условии. Если строка начинается с ?, то это запрос. Далее следуют числа f и t(1 ≤ f, t ≤ n).

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

Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.

Решение.

Это одна из классических задач на ДО. В качестве функции используется сумма.

Код

const int MaxN= 5*100*1000; int a[MaxN+5]; int main() < ios::sync_with_stdio(0); //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int n,q; cin>>n>>q; for (int i=0; i>a[i]; SegmentTree st(n,a); char c; int l,r; int i,d; for (int Q=0; Q>c; if (c=='?') < cin>>l>>r; cout else < //c== '=' cin>>i>>d; st.update(i-1,d); > > return 0; >

2. В стране невыученных уроков

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа l и r, и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от l до r включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие. Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.

Технические условия

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

Первая строка содержит количество элементов n (1 ≤ n ≤ 105) в массиве. Во второй строке находится n чисел – элементы ai (1 ≤ ai ≤ 109) массива. В третьей строке находится количество запросов m (1 ≤ m ≤ 105). Далее в m строках находятся по три числа q, l, r (1 ≤ l ≤ r ≤ n). Если q = 1, требуется посчитать НОД элементов на промежутке [l, r], если q = 2, то надо заменить элемент в позиции l на число r.

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

Для каждого запроса с номером 1 в отдельной строке выведите ответ на запрос. Подсказка. Тут все просто:)

Решение.

Просто напишем функцию наибольшего общего делителя и передадим ее в качестве ассоциативной функции для ДО.

Код.

int gcd(int a, int b) < if (a==0) return b; return gcd(b%a,a); >const int MaxN= 5*100*1000; int a[MaxN+5]; int main() < ios::sync_with_stdio(0); //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int n,q; cin>>n; for (int i=0; i>a[i]; cin>>q; SegmentTree st(n,a,gcd); char c; int l,r; int i,d; for (int Q=0; Q>c; if (c=='1') < cin>>l>>r; cout else < //c== '2' cin>>i>>d; st.update(i-1,d); > > return 0; >

3. Range Variation Query

Последовательность an задается следующей формулой: an = n2 mod 12345 + n3 mod 23456. Требуется много раз отвечать на запросы следующего вида: • найти разность между максимальным и минимальным значением среди элементов ai, ai+1, . aj; • присвоить элементу ai значение j.

Технические условия

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

Первая строка содержит натуральное число k (k ≤ 100 000) — количество запросов. Следующиеk строк содержат запросы, по одному в строке. Запрос номер i описывается двумя целыми числамиxi, yi. Если xi > 0, то требуется найти разность между максимальным и минимальным значением среди элементов axi. ayi. При этом 1 ≤ xi ≤ yi ≤ 100 000. Если xi < 0, то требуется присвоить элементу a-xi значение yi. При этом -100 000 ≤ xi ≤ -1 и |yi| ≤ 100 000.

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

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

Подсказка.

Создать 2 дерева отрезков.

Решение.

В одном будем хранить максимум на отрезке, в другом – минимум. Нам понадобиться лишь написать функции минимума и максимума и передать в качестве 0 для минимума ОЧЕНЬ большое число, для максимума ОЧЕНЬ маленькое.

Код.

 int Max(int a, int b) < return max(a,b); >int Min(int a, int b) < return min(a,b); >const int MaxN= 100000; const int inf= 1000*1000*1000; int a[MaxN+5]; int main() < ios_base::sync_with_stdio(0); cin.tie(0); srand(__rdtsc()); for (LL i=0; istMin(MaxN,a+1,Min,inf); SegmentTree stMax(MaxN,a+1,Max,-inf); int x,y,k; cin>>k; for (int i=0; i>x>>y; if (x>0) cout > return 0; >

4. Можете ли Вы ответить на эти вопросы — 3

Задана последовательность целых чисел a1, a2, . an (|ai| ≤ 10000 , 1 ≤ n ≤ 50000). Над ней Вам следует выполнить m (m ≤ 50000) операций: • модифицировать i-ый элемент последовательности • для заданных x и y вывести MAX

Технические условия

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

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность a1, a2, . an. Третья строка содержит число m. Следующие m строк содержат запросы вида: • 0 x y: изменить ax на y (|y| ≤ 10000). • 1 x y: вывести MAX

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

Для каждого запроса вывести ответ как требуется в задаче.

Подсказка.

Создадим структуру из 4 элементов: сумма на отрезке, максимальная сумма на отрезке (ответ на запрос), максимальная сумма начинающаяся с начала отрезка, максимальная сумма заканчивающаяся в конце отрезка.

Решение.

Создадим на этой структуре ДО. Функцию нужно задать следующим образом: сумма на отрезке, очевидно, равна сумме всех чисел; левая сумма – максимум среди [левая сумма левого отрезка], [сумма всех чисел левого отрезка и левая сумма правого отрезка]; правая сумма – максимум среди [правая сумма правого отрезка], [сумма всех чисел правого отрезка и правая сумма левого отрезка]; максимальная сумма – максимум среди [максимальная сумма левого отрезка, максимальная сумма правого отрезка, правая сумма левого отрезка+левая сумма правого отрезка]

Код.


const int inf= 16000; class Four < public: int leftSum,rightSum,maxSum,sum; Four() < leftSum= -inf; rightSum= -inf; maxSum= -inf; sum= 0; >Four(int a, int b, int c, int d) < leftSum= a; rightSum= b; maxSum= c; sum= d; >>; Four maxSum(Four a, Four b) < Four res; res.leftSum= max(a.leftSum,a.sum+b.leftSum); res.rightSum= max(b.rightSum,b.sum+a.rightSum); res.maxSum= max(a.maxSum,max(b.maxSum,a.rightSum+b.leftSum)); res.sum= a.sum+b.sum; return res; >const int MaxN= 50000; Four a[MaxN+5]; int main() < ios_base::sync_with_stdio(0); cin.tie(0); srand(__rdtsc()); int n; cin>>n; < int t; for (int i=0; i>t; a[i]= Four(t,t,t,t); > > Four zero(-inf,-inf,-inf,0); SegmentTree st(n,a,maxSum,zero); int x,y,m,q; cin>>m; Four t; for (int i=0; i>q>>x>>y; if (q==1) < t= st.query(x-1,y-1); coutelse < st.update(x-1,Four(y,y,y,y)); >> return 0; >

дерево отрезков, segment tree, e-olimp

Источник

Codeforces дерево отрезков задачи

Error_Yuan → About #893 C

pakhomovee → Codeforces Round #893 (Div. 2)

mohit_jx64 → [Invitation] Coding Events — Esya’23 IIIT-Delhi

e-maxx → Codeforces Beta Round #30. Разбор A

PinkieRabbit → AI language models and cheating in online contests

induk_v_tsiane → Codeforces Round #892 (Div. 2) Editorial

abcsumits → Help me to find number of solution of this equation efficiently

WeaponizedAutist → Perhaps you should give up

steveonalex → [Tutorial] Divide and Conquer Offline Query — A Niche Way to solve Static Range Query

RAD → Codeforces Round #113 (Div. 2) Разбор задач

MikeMirzayanov → Filter for Past Contests

ashwanth106121023 → Good Observations:

MrPrince22 → Answer queries for number of subarrays where sum is equal to K

Vladosiya → Codeforces Round #874 (Div. 3) Разбор

R.A.N.K.A. → Help in Permutation P[i]=P[P[i]]

Agnimandur → Codeforces Round 736 Editorial

T heQueenOfHatred → 2023 KSAAC Summer · solved.ac Arena #4 Announcement

K evin114514 → I’m Kevin114514, AMA!

Iuc_Crie → Sigh

G eothermal → I’m Geothermal. AMA!

mauryasunny088 → Help needed in EDU section Question

Vladithur → Codeforces Round #890 (Div. 2) Editorial

awoo → Разбор Educational Codeforces Round 149

mustard_with_fries69420 → Help Needed

maverick_GOD → How to use gcc instead of clang on macOS, specially M1? (Help)

Источник