1. Идея

Нужно смоделировать работу простого текстового редактора с курсором и буфером обмена.

Если хранить весь текст в одной строке и каждый раз вставлять или удалять символ в середине, то операции будут слишком медленными: одна такая команда может стоить O(n), а команд до 2 * 10^5.

Поэтому используется классическая идея с двумя частями строки:

• left_part — символы слева от курсора;
• right_part — символы справа от курсора, но в перевёрнутом порядке.

Тогда:

• курсор находится между left_part и right_part;
• символ сразу слева от курсора — это конец left_part;
• символ сразу справа от курсора — это конец right_part.

Это позволяет быстро выполнять команды LEFT, RIGHT, INS, BS, DEL.

Для команды COPY l r нужно уметь получить подстроку по индексам во всей текущей строке. Для этого время от времени будем собирать:

• left_s — строку из left_part,
• right_s — строку из right_part, но уже в нормальном порядке.

Чтобы не собирать их после каждой команды заново, используются флаги left_dirty и right_dirty: если соответствующая часть менялась, строковое представление нужно пересчитать; если не менялась — можно использовать уже готовое.

2. Наблюдения

Наблюдение 1. Как представить курсор

Если текущий текст равен, например, abc|de, где | — курсор, то можно хранить:

• left_part = ['a', 'b', 'c']
• right_part = ['e', 'd']

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

Тогда:

• LEFT: перенести последний символ из left_part в right_part
• RIGHT: перенести последний символ из right_part в left_part

Обе операции работают за O(1).

Наблюдение 2. Вставка и удаление около курсора

• INS c: просто добавить c в конец left_part
• BS: удалить последний символ из left_part
• DEL: удалить последний символ из right_part

Тоже по O(1).

Наблюдение 3. Команды HOME и END

• HOME: весь текст слева от курсора нужно перенести вправо
• END: весь текст справа от курсора нужно перенести влево

Это делается простыми переносами между двумя массивами.

Хотя одна такая команда может двигать много символов, суммарная длина текста ограничена 10^6, и эталонное решение именно так и моделирует эти команды.

Наблюдение 4. Как делать COPY l r

Полный текст — это:

• сначала left_part в обычном порядке,
• потом right_part в обратном порядке.

Значит, если заранее иметь строки:

• left_s = ''.join(left_part)
• right_s = ''.join(reversed(right_part))

то копирование разбивается на 3 случая:

1. весь отрезок лежит в левой части;
2. весь отрезок лежит в правой части;
3. отрезок пересекает курсор, тогда нужно взять хвост left_s и начало right_s.

Наблюдение 5. Ленивая пересборка строк

После каждой команды пересобирать left_s и right_s невыгодно.

Поэтому:

• если изменилась left_part, ставим left_dirty = true;
• если изменилась right_part, ставим right_dirty = true;
• перед COPY при необходимости пересчитываем только те строки, которые действительно устарели.

3. Алгоритм

Поддерживаем:

• left_part — массив символов слева от курсора;
• right_part — массив символов справа от курсора в обратном порядке;
• clipboard — строку буфера обмена;
• left_s, right_s — строковые представления частей;
• left_dirty, right_dirty — флаги актуальности.

Обработка команд:

LEFT

Если left_part не пуст:

• взять последний символ из left_part,
• добавить его в right_part,
• обе строковые версии становятся неактуальными.

RIGHT

Если right_part не пуст:

• взять последний символ из right_part,
• добавить его в left_part,
• обе строковые версии становятся неактуальными.

BS

Если left_part не пуст:

• удалить последний символ из left_part,
• left_s становится неактуальной.

DEL

Если right_part не пуст:

• удалить последний символ из right_part,
• right_s становится неактуальной.

HOME

Пока left_part не пуст:

• переносить последний символ из left_part в right_part.

После этого обе строковые версии неактуальны.

END

Пока right_part не пуст:

• переносить последний символ из right_part в left_part.

После этого обе строковые версии неактуальны.

INS c

• добавить символ c в конец left_part,
• пометить left_s как неактуальную.

PASTE

• вставить все символы из clipboard в конец left_part,
• если буфер не пуст, left_s становится неактуальной.

COPY l r

Сначала проверяем корректность диапазона:

• 0 <= l <= r <= текущая_длина

Если диапазон некорректен, команда игнорируется.

Иначе:

• если left_s устарела, собираем её из left_part;
• если right_s устарела, собираем её из right_part в правильном порядке;
• пусть left_len = len(left_s).

Дальше:

1. если r <= left_len, вся подстрока в left_s;
2. если l >= left_len, вся подстрока в right_s;
3. иначе подстрока пересекает границу:
   • берём left_s[l:]
   • и right_s[:r - left_len]

В конце выводим:

• left_part в обычном порядке,
• затем right_part в обратном порядке.

4. Почему это работает

Докажем, что структура данных всегда правильно описывает текст и положение курсора.

Инвариант

После обработки любой команды:

• символы текста слева от курсора в правильном порядке лежат в left_part;
• символы текста справа от курсора в правильном порядке равны reversed(right_part).

Значит, весь текст равен:

left_part + reversed(right_part).

Изначально

Строка пуста, курсор в позиции 0.

• left_part = []
• right_part = []

Инвариант выполнен.

Команда INS c

Символ вставляется в позицию курсора и после этого оказывается слева от нового положения курсора. Добавление в конец left_part делает ровно это.

Инвариант сохраняется.

Команда LEFT

Если курсор не в начале, символ непосредственно слева от курсора — это последний символ left_part. После сдвига влево этот символ должен стать первым справа от курсора. Так как right_part хранится в обратном порядке, нужно просто добавить этот символ в конец right_part.

Инвариант сохраняется.

Команда RIGHT

Если курсор не в конце, символ непосредственно справа от курсора — это последний символ right_part. После сдвига вправо он должен стать символом слева от курсора, то есть попасть в конец left_part.

Инвариант сохраняется.

Команда BS

Удаляется символ слева от курсора, то есть последний символ left_part.

Инвариант сохраняется.

Команда DEL

Удаляется символ справа от курсора, то есть последний символ right_part.

Инвариант сохраняется.

Команды HOME и END

• HOME переносит все символы из левой части в правую, значит курсор переходит в начало;
• END переносит все символы из правой части в левую, значит курсор переходит в конец.

Обе команды сохраняют инвариант.

Команда PASTE

Буфер вставляется в позицию курсора, а после вставки курсор оказывается после вставленного текста. Значит, содержимое буфера нужно дописать в конец left_part.

Инвариант сохраняется.

Команда COPY l r

Она не меняет текст и курсор, только обновляет буфер. Значит, на инвариант не влияет.

Теперь разберём корректность копирования.

Полный текст по инварианту равен:

• left_s, затем
• right_s.

Если диапазон l..r-1 корректен, то он:

• либо полностью лежит в left_s,
• либо полностью лежит в right_s,
• либо начинается в left_s, а заканчивается в right_s.

В каждом случае алгоритм берёт ровно нужные символы. Значит, в буфер попадает требуемая подстрока.

Следовательно, после выполнения всех команд итоговая строка будет получена правильно.

5. Сложность

Обозначим через n текущую длину текста.

• LEFT, RIGHT, INS, BS, DEL работают за O(1).
• PASTE работает за O(k), где k — длина буфера.
• HOME и END работают за O(m), где m — сколько символов переносится.
• COPY после возможной пересборки строк работает за O(len copied part) плюс стоимость пересборки left_s и right_s, если они устарели.

Итоговая сборка ответа — O(n).

С учётом ограничения, что в любой момент длина текста не превышает 10^6, такое решение укладывается в лимиты.

По памяти:

• left_part, right_part, clipboard, а также временные строки занимают O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int q;
    cin >> q;
    string dummy;
    getline(cin, dummy);

    vector<char> left_part;
    vector<char> right_part; // reversed
    string clipboard;

    string left_s, right_s;
    bool left_dirty = true;
    bool right_dirty = true;

    for (int step = 0; step < q; step++) {
        string line;
        getline(cin, line);

        if (line == "LEFT") {
            if (!left_part.empty()) {
                right_part.push_back(left_part.back());
                left_part.pop_back();
                left_dirty = true;
                right_dirty = true;
            }
        } else if (line == "RIGHT") {
            if (!right_part.empty()) {
                left_part.push_back(right_part.back());
                right_part.pop_back();
                left_dirty = true;
                right_dirty = true;
            }
        } else if (line == "BS") {
            if (!left_part.empty()) {
                left_part.pop_back();
                left_dirty = true;
            }
        } else if (line == "DEL") {
            if (!right_part.empty()) {
                right_part.pop_back();
                right_dirty = true;
            }
        } else if (line == "HOME") {
            while (!left_part.empty()) {
                right_part.push_back(left_part.back());
                left_part.pop_back();
            }
            left_dirty = true;
            right_dirty = true;
        } else if (line == "END") {
            while (!right_part.empty()) {
                left_part.push_back(right_part.back());
                right_part.pop_back();
            }
            left_dirty = true;
            right_dirty = true;
        } else if (line == "PASTE") {
            for (char c : clipboard) {
                left_part.push_back(c);
            }
            if (!clipboard.empty()) {
                left_dirty = true;
            }
        } else if (line.size() >= 4 && line.substr(0, 4) == "INS ") {
            char c = line[4];
            left_part.push_back(c);
            left_dirty = true;
        } else if (line.size() >= 5 && line.substr(0, 5) == "COPY ") {
            long long l = 0, r = 0;
            int i = 5;
            while (i < (int)line.size() && line[i] != ' ') {
                l = l * 10 + (line[i] - '0');
                i++;
            }
            i++;
            while (i < (int)line.size()) {
                r = r * 10 + (line[i] - '0');
                i++;
            }

            long long len = (long long)left_part.size() + (long long)right_part.size();
            if (0 <= l && l <= r && r <= len) {
                if (left_dirty) {
                    left_s.assign(left_part.begin(), left_part.end());
                    left_dirty = false;
                }
                if (right_dirty) {
                    right_s.assign(right_part.rbegin(), right_part.rend());
                    right_dirty = false;
                }

                long long left_len = (long long)left_s.size();
                if (r <= left_len) {
                    clipboard = left_s.substr((size_t)l, (size_t)(r - l));
                } else if (l >= left_len) {
                    clipboard = right_s.substr((size_t)(l - left_len), (size_t)(r - l));
                } else {
                    string a = left_s.substr((size_t)l, (size_t)(left_len - l));
                    string b = right_s.substr(0, (size_t)(r - left_len));
                    clipboard = a + b;
                }
            }
        }
    }

    string result;
    result.reserve(left_part.size() + right_part.size());
    for (char c : left_part) result.push_back(c);
    for (auto it = right_part.rbegin(); it != right_part.rend(); ++it) {
        result.push_back(*it);
    }

    cout << result << "\n";
    return 0;
}

7. Код на Python 3

q = int(input())

left_part = []
right_part = []  # reversed
clipboard = ""

left_s = ""
right_s = ""
left_dirty = True
right_dirty = True

for _ in range(q):
    line = input()

    if line == "LEFT":
        if left_part:
            right_part.append(left_part.pop())
            left_dirty = True
            right_dirty = True

    elif line == "RIGHT":
        if right_part:
            left_part.append(right_part.pop())
            left_dirty = True
            right_dirty = True

    elif line == "BS":
        if left_part:
            left_part.pop()
            left_dirty = True

    elif line == "DEL":
        if right_part:
            right_part.pop()
            right_dirty = True

    elif line == "HOME":
        while left_part:
            right_part.append(left_part.pop())
        left_dirty = True
        right_dirty = True

    elif line == "END":
        while right_part:
            left_part.append(right_part.pop())
        left_dirty = True
        right_dirty = True

    elif line == "PASTE":
        if clipboard:
            left_part.extend(clipboard)
            left_dirty = True

    elif line.startswith("INS "):
        c = line[4]
        left_part.append(c)
        left_dirty = True

    elif line.startswith("COPY "):
        parts = line.split()
        l = int(parts[1])
        r = int(parts[2])

        total_len = len(left_part) + len(right_part)
        if 0 <= l <= r <= total_len:
            if left_dirty:
                left_s = ''.join(left_part)
                left_dirty = False
            if right_dirty:
                right_s = ''.join(reversed(right_part))
                right_dirty = False

            left_len = len(left_s)
            if r <= left_len:
                clipboard = left_s[l:r]
            elif l >= left_len:
                clipboard = right_s[l - left_len:r - left_len]
            else:
                clipboard = left_s[l:] + right_s[:r - left_len]

print(''.join(left_part) + ''.join(reversed(right_part)))