OJ.UZ: https://oj.uz/problem/view/IOI12_scrivener
BOJ: https://www.acmicpc.net/problem/5812


Persistent한 트리를 구성해주면 된다.
GetLetter를 빠른 속도로 구해야 하는데, LCA를 구할 때 처럼 2배씩 늘려나가며 부모 노드를 계산해주면 쿼리당 O(log |S|)에 가능하다. (S는 현재 문자열)
아래 예시 코드는 BOJ용


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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76#include <iostream> namespace Crayfish { struct Node { int par; int len; char ch; } D[1'000'004]; int cnt; int parents[1'000'004][20]; void Init() { D[0] = {0, 0, '^'}; cnt = 1; } void common() { parents[cnt][0] = D[cnt].par; for (int i = 1; i < 20; ++i) { parents[cnt][i] = parents[parents[cnt][i - 1]][i - 1]; } ++cnt; } void TypeLetter(char ch) { D[cnt] = { cnt - 1, D[cnt - 1].len + 1, ch, }; common(); } void UndoCommands(int n) { D[cnt] = D[cnt - n - 1]; common(); } char GetLetter(int p) { int np = cnt - 1; int l = D[cnt - 1].len - p - 1; for (int i = 0; i < 20; ++i) { if (l & (1 << i)) np = parents[np][i]; } return D[np].ch; } } int main() { using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); Crayfish::Init(); int qn; for (cin >> qn; qn--; ) { int n; char q[4]; cin >> q; switch(q[0]) { case 'T': cin >> q; Crayfish::TypeLetter(q[0]); break; case 'U': cin >> n; Crayfish::UndoCommands(n); break; default: cin >> n; cout << Crayfish::GetLetter(n) << '\n'; } } }