7414. Простое
задание
Это задание
очень простое. Вам дана строка S длины n
и q запросов, каждый запрос имеет
формат i j k, что означает:
отсортировать подстроку, состоящую из символов от i до j, в неубывающем
порядке, если k = 1 или в
невозрастающем порядке, если k = 0.
Выведите
итоговую строку после выполнения запросов.
Вход. В первой строке записано два целых числа n и q
(1 ≤ n ≤ 105,
0 ≤ q ≤ 50000), длина
строки и количество запросов соответственно.
В следующей строке идёт сама строка S. Она состоит только из
строчных английских букв.
В каждой из следующих q
строк записано по три целых числа i, j, k
(1 ≤ i ≤ j ≤ n, k = 0 или k = 1), обозначающих запрос.
Выход. Выведите строку
S после выполнения всех запросов.
|
Пример
входа |
Пример
выхода |
|
10 5 abacdabcda 7 10 0 5 8 1 1 4 0 3 6 0 7 10 1 |
cbcaaaabdd |
РЕШЕНИЕ
дерево отрезков
Анализ алгоритма
Создадим 26
деревьев отрезков сумм, по одному для каждой буквы от ‘a’
до ‘z’. Деревья должны поддерживать множественную модификацию. Например,
для буквы ‘a’ и строки abacdabcda дерево отрезков
выглядит так:
При помощи
такого дерева за логарифмичекое время можно ответить на вопрос: сколько раз
некоторая буква встречается на отрезке [l;
r].
Выполнение
запроса на отрезке [l; r] сводится к сортировке подсчетом. Сначала в массиве cnt подсчитаем
сколько раз каждая буква встречается на отрезке [l;
r].
Реализация алгоритма
Объявим для каждой буквы от ‘a’
до ‘z’ дерево отрезков. Итого будет ALPHABET
= 26 деревьев, поддерживающих операцию суммирования и множественную
модификацию.
#define MAX 100010
#define ALPHABET 26
struct node
{
int summa,
add;
}
SegTree[4*MAX][ALPHABET];
Объявим массив для подсчета количества букв.
int cnt[ALPHABET];
Построение 26 деревьев отрезков по строке s.
void build(int
v, int Left, int
Right)
{
int i;
if (Left ==
Right)
{
SegTree[v][s[Left] - 'a'].summa = 1;
for(i = 0;
i < ALPHABET; i++)
SegTree[v][i].add = -1;
}
else
{
int Middle
= (Left + Right) / 2;
build (v*2, Left, Middle);
build
(v*2+1, Middle+1, Right);
for(i = 0;
i < ALPHABET; i++)
{
SegTree[v][i].summa =
SegTree[v*2][i].summa + SegTree[v*2+1][i].summa;
SegTree[v][i].add = -1;
}
}
}
Вершине v соответствует
отрезок [LeftPos, RightPos], причем Middle = (LeftPos + RightPos) / 2. Произведем проталкивание этой
вершины в дереве отрезков номер Version.
void Push(int
v, int LeftPos, int
Middle, int RightPos, int
Version)
{
if
(SegTree[v][Version].add != -1)
{
SegTree[2*v][Version].add =
SegTree[v][Version].add;
SegTree[2*v][Version].summa =
(Middle - LeftPos + 1) *
SegTree[v][Version].add;
SegTree[2*v+1][Version].add =
SegTree[v][Version].add;
SegTree[2*v+1][Version].summa =
(RightPos - Middle) *
SegTree[v][Version].add;
SegTree[v][Version].add = -1;
}
}
Вершине v соответствует
отрезок [LeftPos, RightPos]. Установим в дереве отрезков номер Version значения элементов с индексами от L до R равными Value.
void SetValue(int
v, int LeftPos, int
RightPos, int L, int
R,
int
Value, int Version)
{
if (L > R) return;
if ((LeftPos
== L) && (RightPos == R))
{
SegTree[v][Version].add = Value;
SegTree[v][Version].summa = (R - L + 1) *
Value;
return;
}
int Middle =
(LeftPos + RightPos) / 2;
Push(v,LeftPos,Middle,RightPos, Version);
SetValue(2*v, LeftPos, Middle, L,
min(Middle,R), Value, Version);
SetValue(2*v+1, Middle+1, RightPos,
max(L,Middle+1), R, Value, Version);
SegTree[v][Version].summa =
SegTree[2*v][Version].summa +
SegTree[2*v+1][Version].summa;
}
Вершине v соответствует
отрезок [LeftPos, RightPos]. Найдем сумму элементов на отрезке
[L; R] в дереве отрезков номер Version.
int Summa(int
v, int LeftPos, int
RightPos, int L, int
R, int Version)
{
if (L > R)
return 0;
if ((LeftPos
== L) && (RightPos == R))
return
SegTree[v][Version].summa;
int Middle =
(LeftPos + RightPos) / 2;
Push(v,LeftPos,Middle,RightPos,Version);
return
Summa(2*v, LeftPos, Middle, L, min(Middle,R), Version) +
Summa(2*v+1, Middle+1, RightPos,
max(L,Middle+1), R, Version);
}
Совершим проталкивание во всех вершинах дерева отрезков
номер Version. Занесем буквы Version
+ 'a' во все места
строки s.
void get(int
v, int LeftPos, int
RightPos, int Version)
{
if
(SegTree[v][Version].summa == 0) return;
if (LeftPos
== RightPos)
{
s[LeftPos] = Version + 'a';
return;
}
int Middle =
(LeftPos + RightPos) / 2;
Push(v,LeftPos,Middle,RightPos,Version);
get(2*v, LeftPos, Middle, Version);
get(2*v+1, Middle+1, RightPos, Version);
}
Основная часть программы. Читаем входные данные. По входной
строке s строим 26 деревьев отрезков, по одному
для каждой буквы.
scanf("%d %d\n",&n,&q);
gets(s+1);
build(1,1,n);
Последовательно обрабатываем q запросов.
for(i = 0; i < q; i++)
{
scanf("%d %d
%d", &l, &r, &command);
Совершим сортировку подсчетом всех букв на отрезке [l; r]. Для этого
сначала подсчитаем количество букв ‘a’ + j на отрезке [l;
r] и занесем это количество в cnt[j].
for(j = 0; j
< ALPHABET; j++)
cnt[j] = Summa(1, 1, n, l, r, j);
Стартуем с позиции pos и движемся
вправо или влево в зависимости от значения command.
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];
}
}
}
Генерируем результирующую строку по содержимому деревьев
отрезов. Функция get(1, 1, n, i) исходя из данных i-го дерева отрезов устанавливает
все буквы ‘a’ + i на свои места в строке s. Функция get производит полное
проталкивание данных – проходит по вершинам дерева отрезков за время O(n).
for(i = 0; i < ALPHABET; i++)
get(1, 1, n, i);
Выводим результирующую строку.
puts(s+1);