Реализовать структуру данных Rope

@Verona19 · Регистрация: 06.09.2015

Студворк — интернет-сервис помощи студентам

задача со степика. может у кого есть решение

Ваша цель в данной задаче — реализовать структуру данных Rope.
Данная структура данных хранит строку и позволяет эффективно вырезать кусок строки и переставить его в другое место.

Формат входа:
Первая строка содержит исходную строку S, вторая — число запросов q.
Каждая из последующих q строк задаёт запрос тройкой чисел i,j,k и означает следующее: вырезать подстроку S[i..j] (где i и j индексируются с нуля) и вставить её после k-го символа оставшейся строки (где k индексируется с единицы), при этом если k = 0, то вставить вырезанный кусок надо в начало.

Формат выхода: Выведите полученную (после всех q запросов) строку.
Ограничения. S содержит только буквы латинского алфавита.
1 ≤ |S| ≤ 300 000;
1 ≤ q ≤ 100 000;
0 ≤ i ≤ j ≤ n−1;
0 ≤ k ≤ n−(j−i+1).

Пример.
Вход:

hlelowrold

2

1 1 2

6 6 7

Выход:
helloworld
hlelowrold → hellowrold → helloworld

Пример.
Вход:

abcdef

2

0 1 1

4 5 0

Выход:
efcabd
abcdef → cabdef → efcabd

@John Prick · 06.05.2022, 16:18

https://onlinegdb.com/2PwPq77_x

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
 
class Query
{
    public Query(int i, int j, int k)
    {
        this.i = i;
        this.j = j;
        this.k = k;
    }
    
    public string Process(string data)
    {
        StringBuilder sb = new StringBuilder(data);
        sb.Remove(i, j - i + 1);
        sb.Insert(k, data.Substring(i, j - i + 1));
        return sb.ToString();
    }
    
    private int i, j, k;
}
 
class Program
{
    static void Main()
    {
        string data = Console.ReadLine();
        int q = int.Parse(Console.ReadLine());
        
        List<Query> queries = new List<Query>();
        for (int i = 0; i < q; ++i)
        {
            int[] ps = Console.ReadLine().Split().Select(n => int.Parse(n)).ToArray();
            queries.Add(new Query(ps[0], ps[1], ps[2]));
        }
        
        foreach (Query query in queries)
            data = query.Process(data);
        Console.WriteLine(data);
    }
}

@OwenGlendower · 06.05.2022, 17:40

John Prick, вы проглядели ключевой момент задания - реализовать структуру данных Rope.

Rope (рус. веревка) — структура данных для хранения строки, представляющая из себя двоичное сбалансированное дерево и позволяющая делать операции вставки, удаления и конкатенации с логарифмической асимптотикой.

@John Prick · 06.05.2022, 20:06

OwenGlendower, а, ну да. Ну реализовал структуру "в лоб" ))

@Verona19 · 10.05.2022, 16:01 **[ТС]**

Сообщение от John Prick

https://onlinegdb.com/2PwPq77_x

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
 
class Query
{
    public Query(int i, int j, int k)
    {
        this.i = i;
        this.j = j;
        this.k = k;
    }
    
    public string Process(string data)
    {
        StringBuilder sb = new StringBuilder(data);
        sb.Remove(i, j - i + 1);
        sb.Insert(k, data.Substring(i, j - i + 1));
        return sb.ToString();
    }
    
    private int i, j, k;
}
 
class Program
{
    static void Main()
    {
        string data = Console.ReadLine();
        int q = int.Parse(Console.ReadLine());
        
        List<Query> queries = new List<Query>();
        for (int i = 0; i < q; ++i)
        {
            int[] ps = Console.ReadLine().Split().Select(n => int.Parse(n)).ToArray();
            queries.Add(new Query(ps[0], ps[1], ps[2]));
        }
        
        foreach (Query query in queries)
            data = query.Process(data);
        Console.WriteLine(data);
    }
}

Failed test #9 of 9. Time limit exceeded

на степике пишет вот такую ошибку (((

@John Prick · 10.05.2022, 16:14

Сообщение от Verona19

на степике пишет вот такую ошибку (((

Вы бы хоть тему прочли. Это не решение вашей задачи.

Новые блоги и статьи Все статьи Все блоги /
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .

@Verona19 1 / 1 / 0 Регистрация: 06.09.2015 Сообщений: 51

	Реализовать структуру данных Rope 06.05.2022, 15:21. Показов 2936. Ответов 5 Метки нет (Все метки) задача со степика. может у кого есть решение Ваша цель в данной задаче — реализовать структуру данных Rope. Данная структура данных хранит строку и позволяет эффективно вырезать кусок строки и переставить его в другое место. Формат входа: Первая строка содержит исходную строку S, вторая — число запросов q. Каждая из последующих q строк задаёт запрос тройкой чисел i,j,k и означает следующее: вырезать подстроку S[i..j] (где i и j индексируются с нуля) и вставить её после k-го символа оставшейся строки (где k индексируется с единицы), при этом если k = 0, то вставить вырезанный кусок надо в начало. Формат выхода: Выведите полученную (после всех q запросов) строку. Ограничения. S содержит только буквы латинского алфавита. 1 ≤ \|S\| ≤ 300 000; 1 ≤ q ≤ 100 000; 0 ≤ i ≤ j ≤ n−1; 0 ≤ k ≤ n−(j−i+1). Пример. Вход: `hlelowrold 2 1 1 2 6 6 7` Выход: `helloworld` hlelowrold → hellowrold → helloworld Пример. Вход: `abcdef 2 0 1 1 4 5 0` Выход: `efcabd` abcdef → cabdef → efcabd 0

@John Prick 2393 / 1922 / 763 Регистрация: 27.07.2012 Сообщений: 5,565
	06.05.2022, 20:06
	OwenGlendower, а, ну да. Ну реализовал структуру "в лоб" )) 0