Title address ：

https://www.acwing.com/problem/content/949/

A long time ago ,DOS3.x Programmers began to understand EDLIN Be tired of . therefore , People began to use their own text editors ⋯⋯ After many years , By chance , Xiao Ming found an editing software at that time . After some simple tests , Xiao Ming was surprised to find ： That software can perform tens of thousands of editing operations per second （ Of course , You can't do this by hand ）！ therefore , Xiao Ming forgets to eat and sleep and wants to make the same thing . Can you help him ？ In order to clarify the goal , Xiao Ming is right about “ Text editor ” Made an abstract definition ：
Text ： from $0$ One or more ASCII Code in closed interval $[32,126]$ A sequence of characters in .
cursor ： A mark used to indicate a position in a piece of text , Can be at the beginning of the text , End of text or between two characters of text .
Text editor ： Composed of a piece of text and a cursor in the text , A data structure that supports the following operations . If this text is empty , Let's say the text editor is empty .

For example, an empty text editor performs operations in turn INSERT(13, “Balanced tree”), MOVE(2),DELETE(5),NEXT(),INSERT(7, “editor”),MOVE(0),GET(16) after , Will be output Bad editor tree.

Your task is ：
Create an empty text editor .
Read some operations from the input file and execute .
For all executed GET operation , Write the specified content to the output file .

Input format ：
The first line of the input file is the number of instructions $t$, Here's what needs to be done $t$ Operations .
among ：
To make the input file easy to read ,Insert Some carriage returns may be inserted into the string of the operation , Please ignore them （ If it's hard to understand this sentence , You can refer to the example ）.
Except for the carriage return , Enter all characters of the file ASCII The codes are in the closed interval $[32,126]$ Inside . And there is no space at the end of the line .
Here we have the following assumptions ：
MOVE The operation does not exceed $50000$ individual ,INSERT and DELETE The total number of operations does not exceed $4000$,PREV and NEXT The total number of operations does not exceed $200000$.
all INSERT The sum of the inserted characters does not exceed $2M$（$1M=1024\times 1024$ byte ）, The correct output file length does not exceed $3M$ byte .
DELETE Operation and GET There must be enough characters after the operation .MOVE、PREV、NEXT The operation must not attempt to move the cursor to an illegal position .
There are no errors in the input file .

Output format ：
Each line of the output file corresponds to each... In the input file in turn Get The output of the instruction .

You can use block linked lists . Block linked list also uses the idea of blocking , Different from ordinary blocking , Block linked list connects each block with a bidirectional linked list , Thus, we can quickly insert and delete the whole block . It is the same as ordinary blocking , The size of each piece is about $O(\sqrt{n})$, among $n$ Is the total length of the text . After we estimate the size of each block , You can open a sentinel node first （ This node is regarded as the $0$ A block ）, Save a character >, And then with two variables $x$ and $y$ Record the number of characters in which block the current cursor is behind . Each block node should store the block stored string , Subscripts of the previous and next nodes of the block , And the length of the string stored in the block . Consider each operation ：
1、MOVE $k$. From $1$ Start counting backwards in blocks $k$ Characters , If $k$ Greater than the string length of the current block , Skip the whole block ; Otherwise, the cursor should stop in the current block ;
2、INSERT $n$. If the cursor is not at the last character of its block , You need to split . Split the node where the cursor is located into two nodes , Make the cursor exactly at the position of the last character of the first split node , Insert... Like this $n$ Characters can be passed directly new Several new nodes , Then deal with the whole block .
3、DELETE $n$. First look at the block where the cursor is , If there is $n$ Characters can be deleted , Direct deletion , Operation is completed ; Otherwise, delete the remaining characters of the block first , Then traverse the block backwards , If more characters need to be deleted than the number of characters owned by the block , Then delete the whole block directly , Until the last block is deleted .
4、GET $n$. And DELETE similar .
Moving forward and backward is simple .

In addition, attention needs to be paid , You need to merge in time , In case the size of each block is too small , In this way, the operation time may degenerate into linear . The way of merging is to directly traverse all blocks , If it is found that it can be merged with the latter partition （ That is, the sum of the number of characters of these two blocks is less than the maximum block size ）, Then merge . This ensures that the number of characters in each block is at the square root level , At the same time, it also ensures that the total number of blocks is also at the square root level .

Don't always new Outgoing node , This wastes space , Instead, you need to recycle the deleted nodes , Go to the recycle bin directly when you need nodes .

The code is as follows ：

#include <iostream>
#include <cstring>
using namespace std;

// N Is the maximum number of characters per block ,M Is the number of blocks 
const int N = 2000, M = 2010;
int n, x, y;
struct Node {
    
    char s[N + 1];
    int c, l, r;
} p[M];
char str[2000010];
//  Node recycle bin 
int q[M], tt;

//  Move the cursor to k Characters 
void move(int k) {
    
  x = p[0].r;
  //  The whole block can jump and move 
  while (k > p[x].c) k -= p[x].c, x = p[x].r;
  y = k;
}

//  stay x Insert... After the node u node 
void add(int x, int u) {
    
  p[u].r = p[x].r, p[p[u].r].l = u;
  p[x].r = u, p[u].l = x;
}

//  Delete u node 
void del(int u) {
    
  p[p[u].l].r = p[u].r;
  p[p[u].r].l = p[u].l;
  p[u].l = p[u].r = p[u].c = 0;
  // u The node has been deleted , Put it in the recycle bin for future use 
  q[tt++] = u;
}

//  Insert str[1:k]
void insert(int k) {
    
  //  If the cursor is not in the last character of its block , Then split its block 
  if (y < p[x].c) {
    
    int u = q[--tt];
    //  take y Put the following characters in the new node 
    for (int i = y + 1; i <= p[x].c; i++)
      p[u].s[++p[u].c] = p[x].s[i];
    //  The number of characters in the current block should be updated 
    p[x].c = y;
    //  Put the new node on x Behind 
    add(x, u);
  }
  int cur = x;
  //  Take a new node each time , Then fill , Until it is filled k Characters 
  for (int i = 1; i <= k; ) {
    
    int u = q[--tt];
    while (p[u].c < N && i <= k)
      p[u].s[++p[u].c] = str[i++];
    add(cur, u);
    cur = u;
  }
}

//  After deleting the cursor k Characters 
void remove(int k) {
    
  if (p[x].c - y >= k) {
    
    //  If there is still k Characters can be deleted , Direct deletion 
    for (int i = y + k + 1, j = y + 1; i <= p[x].c; )
      p[x].s[j++] = p[x].s[i++];
    p[x].c -= k;
  } else {
    
    //  Otherwise, delete the characters behind the cursor of the current block first 
    k -= p[x].c - y;
    p[x].c = y;
    //  Delete the whole block 
    while (p[x].r && k >= p[p[x].r].c) {
    
      int u = p[x].r;
      k -= p[u].c;
      del(u);
    }
    //  Delete the remaining characters 
    int u = p[x].r;
    for (int i = 1, j = k + 1; j <= p[u].c; ) p[u].s[i++] = p[u].s[j++];
    p[u].c -= k;
  }
}

//  After output cursor k Characters 
void get(int k) {
    
  if (p[x].c - y >= k)
    //  If the current block is just enough k Characters , Direct output 
    for (int i = y + 1; i <= y + k; i++) putchar(p[x].s[i]);
  else {
    
    //  Otherwise, first output the character after the cursor of the current block 
    for (int i = y + 1; i <= p[x].c; i++) putchar(p[x].s[i]);
    k -= p[x].c - y;
    int cur = x;
    //  Block by block output 
    while (p[cur].r && k >= p[p[x].r].c) {
    
      int u = p[cur].r;
      for (int i = 1; i <= p[u].c; i++) putchar(p[u].s[i]);
      k -= p[u].c;
      cur = u;
    }
    //  Output the remaining characters 
    int u = p[cur].r;
    for (int i = 1; i <= k; i++) putchar(p[u].s[i]);
  }
  //  Output a line break 
  puts("");
}

void prev() {
    
  if (y > 1) y--;
  else {
    
    x = p[x].l;
    y = p[x].c;
  }
}

void next() {
    
  if (y < p[x].c) y++;
  else {
    
    x = p[x].r;
    y = 1;
  }
}

void merge() {
    
  //  Scan all nodes 
  for (int i = p[0].r; i; i = p[i].r) {
    
    //  If the current node and the following node can be merged , Then merge into the current node , Otherwise, traverse the next node 
    while (p[i].r && p[i].c + p[p[i].r].c <= N) {
    
      int r = p[i].r;
      for (int j = p[i].c + 1, k = 1; k <= p[r].c; )
        p[i].s[j++] = p[r].s[k++];
      //  Be careful , If the node where the cursor is located is merged to the front , Then update the cursor position 
      if (x == r) x = i, y += p[i].c;
      p[i].c += p[r].c;
      del(r);
    }
  }
}

int main() {
    
  for (int i = 1; i < M; i++) q[tt++] = i;
  scanf("%d", &n);

  //  Insert a sentry 
  str[1] = '>';
  insert(1);
  move(1);

  char op[10];
  while (n--) {
    
    int a;
    scanf("%s", op);
    if (!strcmp(op, "Move")) {
    
      scanf("%d", &a);
      move(a + 1);
    } else if (!strcmp(op, "Insert")) {
    
      scanf("%d", &a);
      int i = 1, k = a;
      while (a) {
    
        str[i] = getchar();
        if (32 <= str[i] && str[i] <= 126) i++, a--;
      }
      insert(k);
      merge();
    } else if (!strcmp(op, "Delete")) {
    
      scanf("%d", &a);
      remove(a);
      merge();
    } else if (!strcmp(op, "Get")) {
    
      scanf("%d", &a);
      get(a);
    } else if (!strcmp(op, "Prev")) prev();
    else next();
  }
}

Time complexity of mobile operation $O(\sqrt{k})$, Insert delete and output operation time $O(\sqrt{n})$, Forward and backward time $O(1)$, Space $O(n)$.