[Luogu] p1383 advanced typewriter

Title address ：

https://www.luogu.com.cn/problem/P1383

Title Description ：
Zaomiao started with the latest advanced typewriter . The latest model naturally has different functions from the past , It has Undo function , Terrible! . Please design a program for this advanced typewriter , Support the following $3$ Kind of operation ：
1.T x： Type a lowercase letter at the end of the article $x$.（Type operation ）
2.U x： Undo the last $x$ The first modification operation .（Undo operation ）（ Be careful Query Operation is not a modification operation ）
3.Q x： Ask the number in the current article $x$ Letters and output .（Query operation ）
The article can be regarded as an empty string at the beginning .

Input format ：
The first $1$ That's ok ： An integer $n$, Represents the number of operations .
following $n$ That's ok , One command per line . Ensure that the input command is legal .

Output format ：
Output one letter per line , Express Query The answer to the operation .

Data range ：
about $40\%$ The data of $n\le 200$.
about $100\%$ The data of $n\le 100000$; Guarantee Undo The operation will not be undone Undo operation .

Advanced challenges ：
about $200\%$ The data of $n\le 100000$;Undo The operation can be undone Undo operation .

IOI Challenge ：
You must use an online algorithm to complete the problem .

Obviously, we should use the chairman tree . If the undo operation is not undone Undo operation , Then just roll back the version $x$ Just step by step , And the version number is the length of the string （ The version number of the initial version is $0$）. However, due to the possible cancellation operation in this topic, the previous cancellation operation is cancelled , So when we perform the undo operation , Open a new version directly , This version is equal to $x$ Previous version . Because of this, the information of how long each version string is lost , We need another array to record this information . The code is as follows ：

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
struct Node {
    
    int l, r;
    char ch;
} tr[(N << 2) + N * 17];
// root[i] by i The root subscript of the No. version ,len[i] by i The string length of version number ,ver Number the current version 
int root[N], idx, len[N], ver;

int build(int l, int r) {
    
  int p = ++idx;
  if (l == r) return p;
  int mid = l + r >> 1;
  tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
  return p;
}

int update(int p, int l, int r, int k, char ch) {
    
  int q = ++idx;
  tr[q] = tr[p];

  if (l == r) tr[q].ch = ch;
  else {
    
    int mid = l + r >> 1;
    if (k <= mid) tr[q].l = update(tr[q].l, l, mid, k, ch);
    else tr[q].r = update(tr[q].r, mid + 1, r, k, ch);
  }

  return q;
}

char query(int p, int l, int r, int k) {
    
  if (l == r) return tr[p].ch;
  int mid = l + r >> 1;
  if (k <= mid) return query(tr[p].l, l, mid, k);
  else return query(tr[p].r, mid + 1, r, k);
}

int main() {
    
  cin >> n;
  for (int i = 1; i <= n; i++) {
    
    char op, ch;
    int x;
    cin >> op;
    if (op == 'T') {
    
      cin >> ch;
      ver++;
      len[ver] = len[ver - 1] + 1;
      root[ver] = update(root[ver - 1], 1, n, len[ver], ch);
    } else {
    
      cin >> x;
      if (op == 'U') {
    
        //  For undo , Open a new version directly , It is equivalent to x Pre step version 
        ver++;
        root[ver] = root[ver - x - 1];
        len[ver] = len[ver - x - 1];
      } else cout << query(root[ver], 1, n, x) << '\n';
    }
  }
}

operation $1$ and $3$ Time complexity $O(\log n)$, operation $2$ Time $O(1)$, Space $O(n\log n)$.