Сума (Розбір)

Щоб розв'язати задачу, необхідно реалізувати дерево відрізків, що підтримує групові операції — присвоєння та сумування.

У кожному вузлі дерева в змінній $add$ зберігається значення, присвоєне всім елементам відрізка, що відповідає даному вузлу. Якщо вершина дерева відповідає відрізку [l; r], то сума чисел на цьому відрізку дорівнює add \cdot (r - l + 1).

При виконанні операцій присвоєння та сумування, в процесі спуску по дереву від кореня до листів, значення $add$ у кожній вершині необхідно проштовхувати на наступний рівень дерева.

При виконанні операції присвоєння попередні значення сум у дочірніх вершинах s_1 та s_2, а також значення відкладених присвоєнь a_1 та a_2, втрачаються.

При побудові дерева відрізків змінну $add$ у кожній вершині ініціалізуємо значенням, яке ніколи не буде присвоєно елементам відрізка (наприклад, $-1$).

Реалізація алгоритму

Дерево відрізків зберігається у вигляді масиву SegTree, елементи якого мають тип $node$. Кожна вершина дерева відповідає певному відрізку масиву і зберігає інформацію про цей відрізок.

Структура $node$ містить два поля:

• $sum$ — суму елементів на відповідному відрізку;

• $add$ — значення відкладеного присвоєння (lazy propagation).

Конструктор викликається автоматично при створенні кожної вершини дерева:

• $sum$ ініціалізується нулем, оскільки на етапі побудови у вершині ще не накопичена інформація про значення елементів;

• $add$ ініціалізується значенням $-1$, яке використовується як спеціальний маркер і означає відсутність відкладеного присвоєння. Передбачається, що це значення ніколи не буде реально присвоюватися елементам масиву.

struct node
{
  long long sum, add;
  node() : sum(0), add(-1) {}
};
vector<node> SegTree;

Функція Push виконує проштовхування значення $add$ з вершини $v$ у синів. Якщо add \ne -1, то це значення необхідно проштовхнути на один рівень нижче по дереву. Після завершення проштовхування значення $add$ у вершині $v$ встановлюємо рівним $-1$.

void Push(int v, int lpos, int mid, int rpos)
{

Якщо add = -1, то у вершині $v$ відсутня відкладена операція.

  if (SegTree[v].add == -1) return;

Виконуємо перерахунок значень $add$ та $sum$ у синів вершини $v$.

  SegTree[2*v].add = SegTree[v].add;
  SegTree[2*v].sum = (mid - lpos + 1) * SegTree[v].add;
  SegTree[2*v+1].add = SegTree[v].add;
  SegTree[2*v+1].sum = (rpos - mid) * SegTree[v].add;

Після завершення проштовхування встановлюємо add = -1 у вершині $v$.

  SegTree[v].add = -1;
}

Функція SetValue встановлює всі елементи відрізка [left; right] рівними $val$. Вершині $v$ відповідає відрізок [lpos; rpos].

void SetValue(int v, int lpos, int rpos, int left, int right, int val)
{
    if (left > right) return;

Якщо [left; right] відповідає відрізку [lpos; rpos], який зберігається у вершині дерева, то у цій вершині присвоюємо змінним $add$ та $sum$ відповідні значення.

  if ((lpos == left) && (rpos == right))
  {

    SegTree[v].add = val;
    SegTree[v].sum = (long long)(right - left + 1) * val;
    return;
  }

Знаходимо середину відрізка mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Проведемо проштовхування, якщо $add$ не дорівнює $-1$.

  Push(v, lpos, mid, rpos);

Рекурсивно обробляємо лівого та правого сина поточної вершини дерева відрізків.

  SetValue(2*v, lpos, mid, left, min(mid, right), val);
  SetValue(2*v+1, mid+1, rpos, max(left, mid+1), right, val);

Перераховуємо значення суми у вершині $v$ через значення сум її дітей.

  SegTree[v].sum = SegTree[2*v].sum + SegTree[2*v+1].sum;
}

Функція Summa повертає суму елементів на відрізку [left; right].

Вершині $v$ відповідає відрізок [lpos; rpos].

long long Summa(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;

Якщо [left; right] збігається з відрізком [lpos; rpos], який зберігається у вершині $v$ дерева, повертаємо значення суми в цій вершині.

  if ((lpos == left) && (rpos == right)) 
    return SegTree[v].sum;

Знаходимо середину відрізка mid = (lpos + rpos) / 2.

  int mid = (lpos + rpos) / 2;

Проведемо проштовхування, якщо $add$ не дорівнює $-1$.

  Push(v, lpos, mid, rpos);

Розбиваємо відрізок [lpos; rpos] на два підвідрізки: [lpos; mid] та [mid + 1; rpos]. Рекурсивно обчислюємо суми на цих підвідрізках і складаємо отримані значення.

  return Summa(2*v, lpos, mid, left, min(mid, right)) +
         Summa(2*v+1, mid+1, rpos, max(left, mid+1), right);
}

Основна частина програми. Читаємо вхідні дані. Ініціалізуємо дерево відрізків.

cin >> n >> k;
SegTree.resize(4 * n);

Обробляємо $k$ запитів. Залежно від типу запиту виконуємо або групове присвоєння, або обчислення суми на заданому відрізку.

while (k--)
{
  cin >> c;
  if (c == 'A')
  {
    cin >> l >> r >> x;
    SetValue(1, 1, n, l, r, x);
  }
  else
  {
    cin >> l >> r;
    cout << Summa(1, 1, n, l, r) << endl;
  }
}