ALGO Persistent Stack

#include <iostream>
#include <vector>
#include <algorithm>
namespace Mlxa {
    using namespace std;
    typedef long long               ll;
    typedef long long      ull;

    #define all(x)              begin(x), end(x)
    #define eol                 '\n'
    #define read                cin

    template <ostream &out, class A> inline void
    write (A a)         { out << a; }
    template <ostream &out, class A, class... B> inline void
    write (A a, B... b) { out << a << ' '; write<out>(b...); }
    template <ostream &out, class I> void
    writeseq (I b, I e) { for(I i=b;i!=e;++i) out<<*i<<' '; }

    #define print(...)          write<cout>(__VA_ARGS__)
    #define println(...)        print(__VA_ARGS__, eol);
    #define printseq(...)       writeseq<cout>(__VA_ARGS__), print(eol);
    #ifdef AC
        #define addlog(...)     write<cerr>("[D]\t\t\t\t", __VA_ARGS__, eol);
    #else
        #define addlog(...)     (void(0))
    #endif
}   using namespace Mlxa;



        const ull MAX_V = 2000000;
        const ull LOG_V = 21;

        struct Node
        {
            ll value;
            ull len;
            Node *up[LOG_V];
            Node (ll val, Node *p) : value(val)
            {
                up[0] = p;
                for (ull i = 1; i < LOG_V && up[i - 1]; ++ i)
                    up[i] = up[i - 1]->up[i - 1];
                if (p) len = p->len + 1;
                else   len = 0;
            }
            Node (ll val) : Node(val, nullptr) {}
        }; typedef Node *Ptr;

        Ptr ver[MAX_V];
        ull current = 0;

        void push (ll x)
        {
            ull v = current;
            ver[++ current] = new Node(x, ver[v]);
        }

        void pop ()
        {
            ull v = current;
            if (ver[v])
            ver[++ current] = ver[v]->up[0];
        }

        void undo (ull k)
        {
            ull v = current;
            if (k <= v)
                ver[++ current] = ver[v - k];
        }

        Ptr jump (Ptr c, ull j)
        {
            if (j <= 0) return c;
            if (!c)     return c;

            for (ull k = LOG_V; k != (ull)-1; -- k) {
                if ( (1ll << k) <= j )
                    return jump(c->up[k], j - (1ull << k));
            }
            return c;
        }


        void init ()
        {
            ver[0] = new Node(0);
        }


int main ()
{
    freopen("scrivener.in", "r", stdin);
    freopen("scrivener.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    char command;
    ull x, q;
    char c;
    string answer;
    read >> q;

    for (ull rep = 0; rep < q; ++ rep) {
        read >> command;
        if (command == 'T') {
            read >> c;
            push((ull)c);
        } if (command == 'U') {
            read >> x;
            undo(x);
        } if (command == 'P') {
            read >> x;
            Ptr cur = ver[current];
            if (cur) {
                ull len = cur->len - 1;
                Ptr res = jump(ver[current], len - x);
                if (res)
                    answer += ((char)res->value);
            }
        }
    }

    println(answer);

    return 0;
}