Просте завдання#7414

Просте завдання (Розбір)

Створимо $26$ дерев відрізків для підрахунку сум — по одному для кожної літери від ' $a$ ' до ' $z$ '. Кожне дерево повинно підтримувати множинні модифікації.

Наприклад, для літери ' $a$ ' та рядка " $aba c d ab c d a$ " відповідне дерево відрізків буде виглядати так:

За допомогою такого дерева можна за логарифмічний час визначити, скільки разів задана буква зустрічається на відрізку $[l; r]$ [l; r].

Виконання запиту на відрізку $[l; r]$ [l; r] зводиться до сортування підрахунком. Спочатку в масиві $c n t$ підраховується, скільки разів кожна буква зустрічається на даному відрізку.

Далі, залежно від значення $k$ , ми "перебудовуємо" цю ділянку рядка:

якщо $k = 1$ k = 1, то символи розташовуються в невисхідному порядку — тобто літери від ' $a$ ' до ' $z$ ';
якщо $k = 0$ k = 0, то у спадному порядку, від ' $z$ ' до ' $a$ '.

Для цього на всьому відрізку $[l; r]$ [l; r] для кожної літери ' $a$ ' + $j$ , кількість якої відома з масиву cnt, ми встановлюємо в дереві відрізків відповідну кількість одиниць, починаючи з позиції $l$ (якщо сортуємо за зростанням) або з позиції $r$ (якщо за спаданням).

Наприклад, нехай на позиціях $[10; 17]$ знаходиться підрядок " $a c b d b c ab$ ". Підрахуємо кількість кожної літери на цьому інтервалі:

Літера ' $a$ ' зустрічається $2$ рази;
Літера ' $b$ ' зустрічається $3$ рази;
Літера ' $c$ ' зустрічається $2$ рази;
Літера ' $d$ ' зустрічається $1$ раз;

Щоб відсортувати літери на відрізку за зростанням, необхідно для дерева відрізків кожної літери спочатку занулити значення на інтервалі $[10; 17]$ , а потім виконати наступні операції:

Для літери ' $a$ ' на відрізку $[10; 11]$ кожному елементу присвоїти $1$ ;
Для літери ' $b$ ' на відрізку $[12; 14]$ кожному елементу присвоїти $1$ ;
Для літери ' $c$ ' на відрізку $[15; 16]$ кожному елементу присвоїти $1$ ;
Для літери ' $d$ ' на відрізку $[17; 17]$ кожному елементу присвоїти $1$ ;

Таке "оновлення" дерев відрізків фактично моделює перестановку символів на потрібному відрізку без безпосередньої зміни самого рядка.

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

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

Для кожної літери від ' $a$ ' до ' $z$ ' створимо власне дерево відрізків. Таким чином, всього використовується $A L P H A B E T = 26$ ALPHABET = 26 дерев, кожне з яких підтримує операції сумування і множинну модифікацію.

#define MAX 100010
#define ALPHABET 26
struct node
{
  int sum, add;
} SegTree[4*MAX][ALPHABET];

Оголосимо масив для підрахунку кількості входжень кожної літери.

int cnt[ALPHABET];

Побудуємо $26$ дерев відрізків по рядку $s$ — по одному для кожної літери латинського алфавіту.

void build(int v, int lpos, int rpos)
{
  if (lpos == rpos)
  {
    SegTree[v][s[lpos] - 'a'].sum = 1;
    for (int i = 0; i < ALPHABET; i++)
      SegTree[v][i].add = -1;
  }
  else
  {
    int mid = (lpos + rpos) / 2;
    build(v * 2, lpos, mid);
    build(v * 2 + 1, mid + 1, rpos);
    for (int i = 0; i < ALPHABET; i++)
    {
      SegTree[v][i].sum = 
             SegTree[v * 2][i].sum + SegTree[v * 2 + 1][i].sum;
      SegTree[v][i].add = -1;
    }
  }
}

C++

Вершині $v$ відповідає відрізок $[l p os, r p os]$ [lpos, rpos], при цьому $mi d = (l p os + r p os) /2$ mid = (lpos + rpos) / 2. Виконаємо пропихання цієї вершини в дереві відрізків з номером $v er$ .

void Push(int v, int lpos, int mid, int rpos, int ver)
{
  if (SegTree[v][ver].add != -1)
  {
    SegTree[2 * v][ver].add = SegTree[v][ver].add;
    SegTree[2 * v][ver].sum = (mid - lpos + 1) * SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].add = SegTree[v][ver].add;
    SegTree[2 * v + 1][ver].sum = (rpos - mid) * SegTree[v][ver].add;
    SegTree[v][ver].add = -1;
  }
}

C++

Вершині $v$ відповідає відрізок $[l p os, r p os]$ [lpos, rpos]. В дереві відрізків з номером $v er$ встановимо значення $v a l$ для всіх елементів з індексами від $l e f t$ до $r i g h t$ .

void SetValue(int v, int lpos, int rpos, int left, int right, 
              int val, int ver)
{
  if (left > right) return;
  if ((lpos == left) && (rpos == right))
  {
    SegTree[v][ver].add = val;
    SegTree[v][ver].sum = (right - left + 1) * val;
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

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

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

C++

Вершині $v$ відповідає відрізок $[l p os, r p os]$ [lpos, rpos]. Знайдемо суму елементів на відрізку $[l e f t; r i g h t]$ [left; right] в дереві відрізків з номером $v er$ .

int Summa(int v, int lpos, int rpos, int left, int right, int ver)
{
  if (left > right) return 0;
  if ((lpos == left) && (rpos == right)) return SegTree[v][ver].sum;

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

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

C++

Виконаємо пропихання у всіх вершинах дерева відрізків з номером $v er$ . Потім внесемо букву $v er$ + ' $a$ ' у всі позиції рядка $s$ , де її значення в дереві відрізків $v er$ дорівнює $1$ .

void get(int v, int lpos, int rpos, int ver)
{
  if (SegTree[v][ver].sum == 0) return;
  if (lpos == rpos)
  {
    s[lpos] = ver + 'a';
    return;
  }

  int mid = (lpos + rpos) / 2;
  Push(v, lpos, mid, rpos, ver);

  get(2 * v, lpos, mid, ver);
  get(2 * v + 1, mid + 1, rpos, ver);
}

C++

Основна частина програми. Читаємо вхідні дані. За вхідним рядком $s$ будуємо $26$ дерев відрізків — по одному для кожної літери латинського алфавіту.

cin >> n >> q;
cin >> s;
s = " " + s;
build(1,1,n);

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

for (i = 0; i < q; i++)
{
  cin >> l >> r >> command;

Виконаємо сортування підрахунком всіх літер на відрізку $[l; r]$ [l; r]. Для цього спочатку підрахуємо кількість входжень кожної літери ' $a$ ' + $j$ на даному інтервалі і запишемо результат у $c n t [j]$ .

  for (j = 0; j < ALPHABET; j++)
    cnt[j] = Summa(1, 1, n, l, r, j);

Потім, починаючи з позиції $p os$ , будемо рухатися вправо або вліво залежно від значення змінної $co mman d$ .

  pos = (command == 1) ? l : r;
  for (j = 0; j < ALPHABET; j++)
  {
    if (!cnt[j]) continue;
    SetValue(1, 1, n, l, r, 0, j);
    if (command)
    {
      SetValue(1, 1, n, pos, pos + cnt[j] - 1, 1, j);
      pos += cnt[j];
    }
    else
    {
      SetValue(1, 1, n, pos - cnt[j] + 1, pos, 1, j);
      pos -= cnt[j];
    }
  }
}

C++

Генерація підсумкового рядка виконується на основі вмісту дерев відрізків. Функція $g e t (1, 1, n, i)$ get(1, 1, n, i), використовуючи дані $i$ -го дерева відрізків, розставляє всі літери ' $a$ ' + $i$ на відповідні позиції рядка $s$ . Функція get виконує повне пропихання даних, проходячи по всіх вершинах дерева відрізків за час $O (n)$ .

for (i = 0; i < ALPHABET; i++)
  get(1, 1, n, i);

Виводимо підсумковий рядок.

cout << s.substr(1);