WasylF's blog

By WasylF, 10 years ago, In Russian

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

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; }
  • Vote: I like it
  • +7
  • Vote: I do not like it