P1383 高级打字机

题目描述

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下3种操作：
1.T x：在文章末尾打下一个小写字母x。(type操作)
2.U x：撤销最后的x次修改操作。（Undo操作）
（注意Query操作并不算修改操作）
3.Q x：询问当前文章中第x个字母并输出。（Query操作）
文章一开始可以视为空串。

Solution

将每个T操作和U操作建一个节点,
对于Q操作, 使用 $vector[]$ 将该问题编号, 保存在上一个操作节点中
最后离线DFS, 即可 $O(N)$ 处理出每个答案

(这个算法暂且叫它离线树吧…)

Code

#include<bits/stdc++.h>
#define reg register
#define pb push_back

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 100005;

int N;
int num0, cnt_node, cnt_q;
int head[maxn];
int Ans[maxn];
int que_v[maxn];
char S[maxn];
std::vector <int> que_2[maxn];

struct Edge{
        int nxt, to;
        char w;
        Edge(int nxt=0,int to=0,char w='#'):nxt(nxt), to(to), w(w) {}
} edge[maxn << 1];

void Add(int from, int to, char w){
        edge[num0] = Edge(head[from], to, w);
        head[from] = num0 ++;
}

void DFS(int k, int len){
        int size = que_2[k].size();
        for(reg int i = 0; i < size; i ++) Ans[que_2[k][i]] = S[que_v[que_2[k][i]]];
        for(reg int i = head[k]; ~i; i = edge[i].nxt){
                int to = edge[i].to;
                if(edge[i].w != '#'){
                        S[len + 1] = edge[i].w;
                        DFS(to, len+1);
                }else   DFS(to, len);
        }
}

int main(){
        N = read();
        char opt[3];
        memset(head, -1, sizeof head);
        int last = 0;
        for(reg int i = 1; i <= N; i ++){
                scanf("%s", &opt);
                if(opt[0] == 'T'){
                        scanf("%s", opt);       //reuse opt
                        Add(last, ++ cnt_node, opt[0]);
                }
                else if(opt[0] == 'Q') que_2[last].pb(++ cnt_q), que_v[cnt_q] = read();
                else if(opt[0] == 'U') Add(cnt_node - read() - 1, ++ cnt_node, '#');
                last = cnt_node;
        }
        DFS(0, 0);
        for(reg int i = 1; i <= cnt_q; i ++) printf("%c
", Ans[i]);
        return 0;
}