NOIP-EMU-140315-type 高级打字机

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>

using namespace std;
const int maxn = 100100;

// Attempted to create an abstruse name...
class EulerTraversal
{
public:
    char    data[maxn], // Static data of Type() functions
            stk[maxn]; // Temporary stack
    int     pend_answer[maxn], // Pended answer for final dump. Do not use CHAR!
            par[maxn]; // Node parent
    // A in-verbose graph implementation from scratch
    int     graph_edges[maxn], // FIXME:???
            graph_next[maxn], // FIXME:???
            graph_to[maxn]; // FIXME:???
    vector<int> pend_queries[maxn]; // Inserts # of queries
    int     data_idx, edge_idx, pend_ans_idx;
    void insert_edge(int u, int v)
    {
        int p = ++edge_idx; // Assigned new edge id
        // Literally... addedge(u, v).
        graph_next[p] = graph_edges[u];
        graph_edges[u] = p;
        graph_to[p] = v;
        return ;
    }
    void pend_type(char ch)
    {
        // Set original data with ch.
        data[data_idx] = ch;
        data_idx++; // and update id / count
        // Link parent to direct parent (as in the chain)
        par[data_idx] = data_idx - 1;
        return ;
    }
    void pend_undo(int steps)
    {
        data_idx++;
        int parent = data_idx - steps - 1;
        this->insert_edge(parent, data_idx);
        par[data_idx] = parent;
        return ;
    }
    void pend_query(int pos)
    {
        // Assign a new index for this query id.
        pend_queries[data_idx].push_back(++pend_ans_idx);
        // The pended answer is now the query param, and will be updated
        // in eval() function.
        pend_answer[pend_ans_idx] = pos;
        return ;
    }
    void eval(void)
    {
        int pos = 0; // Current stack pointer
        for (int p = 0; ; ) { // p starts from root
            if (graph_edges[p]) {
                int v = graph_to[graph_edges[p]];
                // Remove this 'undo' operation from graph.
                graph_edges[p] = graph_next[graph_edges[p]];
                // Go to target (i.e. linked undo parent), forcefully.
                p = v; continue;
            }
            // If current position is on the chain
            if (data[p] != (char)0) {
                // Append type operation to stack
                stk[++pos] = data[p];
                // Mark original data as used (no duplications, guranteed)
                data[p] = 0;
                // Increment / traverse to child... forcefully.
                p++; continue;
            }
            // Flush results to node queries
            for (unsigned int i = 0; i < pend_queries[p].size(); i++) {
                // v is the assigned query id.
                int v = pend_queries[p][i];
                // As it is, the original value is the param, i.e. query(...[v])
                // which will be converted into actual datum.
                pend_answer[v] = stk[pend_answer[v]];
            }
            // Traverse to parent if is on a chain
            if (par[p] + 1 == p)
                pos--; // Pop in stack
            // Break when reached root
            if (p == 0)
                return ;
            p = par[p];
        }
        return ;
    }
    void flush(void)
    {
        // Flush pre-calculated answers
        for (int i = 1; i <= pend_ans_idx; i++)
            printf("%c\n", pend_answer[i]);
        return ;
    }
} graph;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    // Process the operations offline.
    // Online implementation is **WAY HARDER** to write!
    for (int idx = 1; idx <= n; idx++) {
        char str1[64], str2[64];
        int tmp1;
        scanf("%s", str1);
        if (str1[0] == 'T') {
            scanf("%s", str2);
            graph.pend_type(str2[0]);
        } else if (str1[0] == 'U') {
            scanf("%d", &tmp1);
            graph.pend_undo(tmp1);
        } else if (str1[0] == 'Q') {
            scanf("%d", &tmp1);
            graph.pend_query(tmp1);
        }
    }
    graph.eval();
    // Flushing results in buffer
    graph.flush();
    return 0;
}

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
const int maxn = 100100;

char stk[maxn];
int n, top;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int idx = 1; idx <= n; idx++) {
        char str1[64], str2[64];
        int tmp1;
        scanf("%s", str1);
        if (str1[0] == 'T') {
            scanf("%s", str2);
            stk[++top] = str2[0];
        } else if (str1[0] == 'U') {
            scanf("%d", &tmp1);
            top = max(0, top - tmp1);
        } else if (str1[0] == 'Q') {
            scanf("%d", &tmp1);
            printf("%c\n", stk[tmp1]);
        }
    }
    return 0;
}