Біббл і Капітан Снеппі#4486

Біббл і Капітан Снеппі (Розбір)

Побудуємо дерево відрізків, яке підтримує операцію підсумовування. У кожній вершині (фундаментальному відрізку $[a; b]$ ) додатково будемо зберігати значення $l e f t$ . Якщо $l e f t > 0$ left > 0, то у вершині $[a; b]$ є відкладена операція: всім вершинам її піддерева слід призначити значення $l e f t, l e f t + 1, ..., l e f t + b - a$ left, left + 1, ..., left + b - a. Спочатку $l e f t$ у всіх вершинах дорівнює нулю.

Розглянемо процедуру просування значень. Нехай запит $q (x, y)$ q(x, y) частково перетинає обидва піддерева, тобто $x \leq m < y$ x \le m < y. У цьому випадку:

Для лівого сина встановлюємо $l e f t = 1$ left = 1.
Для правого сина значення $l e f t$ встановлюємо на $1$ більшим довжини відрізка $[x; m]$ .

Якщо $a \neq = x (b \neq = y)$ a \ne x~(b \ne y), то значення $l e f t$ слід просувати далі.

Якщо $x \geq m + 1$ x \ge m + 1 (відрізок запиту повністю лежить у правому піддереві), то значення $l e f t$ для лівого сина залишається рівним $0$ .

Нехай запит $q (x, y)$ q(x, y) покривається набором фундаментальних відрізків $[a_{1}, b_{1}], [a_{2}, b_{2}], ..., [a_{k}, b_{k}]$ [a_1, b_1], [a_2, b_2], ..., [a_k, b_k]. Тоді значення $l e f t$ для відрізка $[a_{i}, b_{i}]$ [a_i, b_i] встановлюємо рівним

1 + сума довжин всіх попередніх відрізків [a_{j}, b_{j}], дляяких j < i

1~+~сума~довжин~всіх~попередніх~відрізків~[a_j,b_j],~для яких~j < i

Наприклад, нехай дерево побудоване на відрізку $[1..8]$ , а запит $q (2, 7)$ q(2, 7) покриває такі фундаментальні відрізки:

Приклад

Розглянемо наступний тест:

Біля кожної вершини в прямокутнику записана сума на відрізку.

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

Оголосимо масив $S e g T r ee$ SegTree для зберігання дерева відрізків.

struct node
{
  long long summa;
  int left;
};
vector<node> SegTree;

Функція BuildTree будує дерево відрізків.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v].sum = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2 * v, lpos, mid);
    BuildTree(2 * v + 1, mid + 1, rpos);
    SegTree[v].sum = SegTree[2 * v].sum + SegTree[2 * v + 1].sum;
  }
}

C++

Функція Sum обчислює суму чисел від $a$ до $b$ .

long long Sum(int a, int b)
{
  return 1LL * (a + b) * (b - a + 1) / 2;
}

Функція Push виконує просування значення $l e f t$ з вершини $v$ в її синів. Виконується перерахунок суми $s u m$ в синах.

void Push(int v, int lpos, int mid, int rpos)
{
  if (SegTree[v].left)
  {
     SegTree[2 * v].left = SegTree[v].left;
     SegTree[2 * v].sum = Sum(SegTree[2 * v].left, 
                              SegTree[2 * v].left + mid - lpos);

     SegTree[2 * v + 1].left = SegTree[v].left + mid - lpos + 1;
     SegTree[2 * v + 1].sum = Sum(SegTree[2 * v + 1].left, 
                        SegTree[2 * v + 1].left + rpos - mid - 1);
     SegTree[v].left = 0;
  }
}

C++

Функція Update заповнює проміжок $[l e f t; r i g h t]$ [left; right] послідовністю значень $f r o m, f r o m + 1, f r o m + 2, ...$ from, from + 1, from + 2, ... .

void Update(int v, int lpos, int rpos, int left, int right, int from)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
  {
    SegTree[v].left = from;
    SegTree[v].sum = Sum(from, from + right - left);
    return;
  }

  int mid = (lpos + rpos) / 2;
  int midval = mid - left + 1;

C++

Якщо відрізок запиту $[l e f t; r i g h t]$ [left; right] повністю лежить в правому піддереві $[mi d + 1; r p os]$ [mid + 1; rpos], то передаємо правому сину значення $f r o m$ без змін (при цьому $mi d v a l$ встановлюємо рівним нулю).

  if (midval < 0) midval = 0;
  Push(v, lpos, mid, rpos);
  Update(2 * v, lpos, mid, left, min(mid, right), from);
  Update(2 * v + 1, mid + 1, rpos, max(left, mid + 1), 
                             right, from + midval);
  SegTree[v].sum = SegTree[2 * v].sum + SegTree[2 * v + 1].sum;
}

C++

Функція Summa повертає суму чисел на відрізку $[l e f t; r i g h t]$ [left; right].

long long Summa(int v, int lpos, int rpos, int Left, int Right)
{
  if (Left > Right) return 0;
  if ((lpos == Left) && (rpos == Right)) return SegTree[v].sum;
    
  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos);

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

C++

Основна частина програми. Читаємо вхідний масив чисел.

scanf("%d", &n);
a.resize(n + 1);
for(i = 1; i <= n; ++i)
  scanf("%d", &a[i]);

Будуємо дерево відрізків.

SegTree.resize(4 * n);
BuildTree(1, 1, n);

Послідовно обробляємо $q$ запитів.

scanf("%d", &q);
for(i = 0; i < q; ++i)
{
  scanf("%d %d %d", &type, &l, &r);
  if(type == 1)
    printf("%lld\n", Summa(1,1,n,l,r));
  else
    Update(1,1,n,l,r,1);
}

C++