Оптимизация строковых операций

Ищу оптимальные сдвиги

Перевожу задачу с русского языка и анализирую образец ввода и вывода. Интересно, как сдвиги подстрок помогают в C++.

Перемещаю подстроку

Смотрю на строку из 7 символов и вижу, что нужно переместить подстроку с позиций 3 по 5 в конец.

Перемещение и изменение

Я анализирую результат операции 1 и замечаю, что строка A Y B A B T U заменена на A Y T U B A B. Это наводит на мысль о возможной ошибке в анализе.

Перемещая символы

Сначала я перемещаю подстроку с позиций 3-5 в конец. Теперь остаются символы на позициях 1-2 и 6-7. Затем я перебрасываю символы с позиций 3-5 в конец.

Оценка операций

Интересно, что требуется обработать до миллиона операций над строкой, что влечет за собой необходимость использовать сбалансированные деревья для эффективного выполнения операций split и merge.

Размышляю над структурами

Я думаю о том, что структура данных Rope или Treap подходит для объединения строк и операций с подстроками. Hm, это особенно актуально для операций, таких как разделение и объединение последовательностей, а также перемещение подстроки.

Перемещение подстроки

Перемещение подстроки [a,b] в конец строки можно выполнить с помощью операций split и merge, используя бинарное дерево поиска с извилинами (treap) для эффективной работы в O(log n) времени.

Формирование дерева

Я собираюсь создать неявное дерево (treap), где узлы представляют символы, а поддеревья отслеживают размеры. Планирую операции разделения и слияния двух деревьев.

Создание структуры и функций

Планирую на C++ создать структуру узла для treap с полями для левых и правых дочерних указателей, размера поддерева и символа. Определяю функции обновления, разделения и слияния.

Построение плана

Читаю n и q, затем создаю треап, разбираюсь с операциями, определяю случайные приоритеты и вывожу треап в порядке.

To solve the problem efficiently, we need to perform substring movements in optimal time. Using a naive approach would result in a time complexity of O(nq), which is not acceptable for large values of $n$ and $q$. Therefore, we will use a data structure called an Implicit Treap (also known as a Cartesian Tree), which allows us to perform split and merge operations in $O(\log n)$ time.

An Implicit Treap is a balanced binary search tree that doesn't store keys explicitly but uses the in-order traversal index as the key. This allows us to represent sequences and perform operations like split, merge, and move efficiently.

Here's how we'll approach the problem:

1. Build the Treap: Construct the treap from the input string, where each node represents a character.

2. Process Queries: For each operation to move a substring $[a, b]$ to the end, we:

   • Split the treap at position $b$ to get two subtrees: $\text{left}$ and $\text{right}$.
   • Split the $\text{left}$ subtree at position $a-1$ to get $\text{left1}$ and $\text{mid}$.
   • Merge $\text{left1}$ and $\text{right}$ to form a new treap without the substring.
   • Merge the new treap with $\text{mid}$ (the substring to move) to place it at the end.

3. Output the Result: Perform an in-order traversal of the final treap to get the resulting string.

Below is the C++ code implementing the above approach:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <random>
#include <string>

using namespace std;

struct Node {
    char val;
    int prior, size;
    Node *left, *right;

    Node(char val) : val(val), prior(rand()), size(1), left(nullptr), right(nullptr) {}
};

int getSize(Node* t) {
    return t ? t->size : 0;
}

void update(Node* t) {
    if (t) {
        t->size = 1 + getSize(t->left) + getSize(t->right);
    }
}

void split(Node* t, int k, Node*& left, Node*& right) {
    if (!t) {
        left = right = nullptr;
    } else {
        int leftSize = getSize(t->left);
        if (k <= leftSize) {
            split(t->left, k, left, t->left);
            right = t;
        } else {
            split(t->right, k - leftSize - 1, t->right, right);
            left = t;
        }
        update(t);
    }
}

void merge(Node*& t, Node* left, Node* right) {
    if (!left || !right) {
        t = left ? left : right;
    } else if (left->prior > right->prior) {
        merge(left->right, left->right, right);
        t = left;
    } else {
        merge(right->left, left, right->left);
        t = right;
    }
    update(t);
}

void inorder(Node* t, string& res) {
    if (!t) return;
    inorder(t->left, res);
    res += t->val;
    inorder(t->right, res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    Node* treap = nullptr;
    for (char c : s) {
        Node* newNode = new Node(c);
        merge(treap, treap, newNode);
    }

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;

        Node *left, *mid, *right;

        split(treap, b, left, right);
        split(left, a - 1, left, mid);

        merge(treap, left, right);
        merge(treap, treap, mid);
    }

    string result;
    inorder(treap, result);
    cout << result << '\n';

    return 0;
}

Explanation:

• Struct Node: Represents a node in the treap with a character value, priority for balancing, size of the subtree, and pointers to left and right children.

• getSize and update: Helper functions to maintain the size property of each node.

• split: Splits the treap into two based on the in-order position $k$.

• merge: Merges two treaps into one, maintaining the heap property based on priority.

• inorder: Performs an in-order traversal to reconstruct the string from the treap.

• Main Function:

  • Reads input and constructs the initial treap.
  • Processes each query by splitting and merging the treap accordingly.
  • Outputs the final string after performing all operations.

Note: We use rand() for priority generation, which is acceptable here, but for better randomness, consider using mt19937 from <random>.

Sample Input:

7 2
AYBABTU
3 5
3 5

Sample Output:

AYABTUB

This code efficiently handles up to $10^6$ operations with a time complexity of $O(q \log n)$, which is suitable for the problem constraints.