高級打字機

luogu 1383

題目大意：

有三種操作：添加一個字符（更改操作），撤回前$i$步步更改操作（更改操作，可以撤回自己），輸出某一位的字符，現在要按要求輸出字符

原題：

題目描述

早苗入手了最新的高級打字機。最新款自然有著與以往不同的功能，那就是它具備撤銷功能，厲害吧。
請為這種高級打字機設計一個程序，支持如下3種操作：
1.T x：在文章末尾打下一個小寫字母x。(type操作)
2.U x：撤銷最后的x次修改操作。（Undo操作）
3.Q x：詢問當前文章中第x個字母并輸出。（Query操作）
文章一開始可以視為空串。

輸入輸出格式

輸入格式：

第1行：一個整數n，表示操作數量。
以下n行，每行一個命令。保證輸入的命令合法。

輸出格式：

每行輸出一個字母，表示Query操作的答案。

輸入輸出樣例

輸入樣例#1：

7 T a T b T c Q 2 U 2 T c Q 2

輸出樣例#1：

b c

說明

【數據范圍】

對于20%的數據 n<=200;
對于50%的數據 n<=100000；保證Undo操作不會撤銷Undo操作。

<高級挑戰>

對于100%的數據 n<=100000；Undo操作可以撤銷Undo操作。

<IOI挑戰>

必須使用在線算法完成該題。

解題思路：

把每一次更改操作當做一個點，當撤銷時就連接撤銷到的點，然后輸出就取最近一次更改操作的結果

代碼：

#include<map> #include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,o,k,y,w,tot,head[100005],ans[100005]; char x,t[100005],c[100005]; map<int, map<int,int> >p; struct rec {int to,next; }a[100005]; void dfs(int dep,int lon) {for (int i=head[dep];i;i=a[i].next)//撤銷的dfs(a[i].to,lon);if (t[dep]) c[lon]=t[dep],dfs(dep+1,lon+1);//添加字符for (int i=1;i<=p[dep][0];++i)ans[p[dep][i]]=c[ans[p[dep][i]]];//記錄 } int main() {scanf("%d",&n);for (int i=1;i<=n;++i){cin>>x;if (x=='T') cin>>t[k++],o=k;else if (x=='U'){k++;scanf("%d",&y);a[++tot].to=k;//連接a[tot].next=head[k-y-1];head[k-y-1]=tot;o=k;//更新}if (x=='Q'){scanf("%d",&y);p[o][++p[o][0]]=++w;//連接的是第幾個輸出ans[w]=y;//初值設為他要求的字符是第幾個，然后記錄答案時直接帶替即可}}dfs(0,1);for (int i=1;i<=w;++i)putchar(ans[i]),putchar(10);//輸出 } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【搜索树】高级打字机（luogu 1383）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。