Данный пост продолжение этого
Для решения будет использоваться мой код класса дерево отрезков единичная модификация.
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<n; i++)
cin>>a[i];
SegmentTree<int> st(n,a);
char c;
int l,r;
int i,d;
for (int Q=0; Q<q; Q++)
{
cin>>c;
if (c=='?')
{
cin>>l>>r;
cout<<st.query(l-1,r-1)<<endl;
}
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<n; i++)
cin>>a[i];
cin>>q;
SegmentTree<int> st(n,a,gcd);
char c;
int l,r;
int i,d;
for (int Q=0; Q<q; Q++)
{
cin>>c;
if (c=='1')
{
cin>>l>>r;
cout<<st.query(l-1,r-1)<<endl;
}
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; i<=MaxN; i++)
a[i]= i*i % 12345 + i*i*i % 23456;
SegmentTree<int> stMin(MaxN,a+1,Min,inf);
SegmentTree<int> stMax(MaxN,a+1,Max,-inf);
int x,y,k;
cin>>k;
for (int i=0; i<k; i++)
{
cin>>x>>y;
if (x>0) cout<<(stMax.query(x-1,y-1)-stMin.query(x-1,y-1))<<endl;
else
{
stMin.update(-x-1,y);
stMax.update(-x-1,y);
}
}
return 0;
}
4. Можете ли Вы ответить на эти вопросы — 3
Задана последовательность целых чисел a1, a2, ..., an (|ai| ≤ 10000 , 1 ≤ n ≤ 50000). Над ней Вам следует выполнить m (m ≤ 50000) операций: • модифицировать i-ый элемент последовательности • для заданных x и y вывести MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}
Технические условия
Входные данные
Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность a1, a2, ..., an. Третья строка содержит число m. Следующие m строк содержат запросы вида: • 0 x y: изменить ax на y (|y| ≤ 10000). • 1 x y: вывести MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}
Выходные данные
Для каждого запроса вывести ответ как требуется в задаче.
Подсказка.
Создадим структуру из 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<n; i++)
{
cin>>t;
a[i]= Four(t,t,t,t);
}
}
Four zero(-inf,-inf,-inf,0);
SegmentTree<Four> st(n,a,maxSum,zero);
int x,y,m,q;
cin>>m;
Four t;
for (int i=0; i<m; i++)
{
cin>>q>>x>>y;
if (q==1)
{
t= st.query(x-1,y-1);
cout<<t.maxSum<<endl;
}
else
{
st.update(x-1,Four(y,y,y,y));
}
}
return 0;
}
Comments (0)
