鹏鹏的旧OI博客

高二及以前的哦,只剩文字了,图片、附件等都没了



高级打字机

题目描述

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

输入

第 1 行:一个整数 n,表示操作数量。
以下 n 行,每行一个命令。保证输入的命令合法。

输出

每行输出一个字母,表示 Query 操作的答案

样例输入

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

样例输出

b
c

数据范围

对于 40%的数据 n<=200;
对于 100%的数据 n<=100000;保证 Undo 操作不会撤销 Undo 操作。
<高级挑战>
对于 200%的数据 n<=100000;Undo 操作可以撤销 Undo 操作。
<IOI 挑战>
必须使用在线算法完成该题。


对于100%的数据,模拟就好了。
对于200%的数据,需要Trie+倍增,反正我是不懂的啦。
另外一个正解是主席树,还好之前写过,现在至少还看得懂233333。
因为主席树是可持续化的,所以撤销操作只要把根指针指回去,添加操作只要新开一棵树就行了。
本来挺好打的代码,结果被len[len[0]]坑了,整整调试了2天才发现mdzz,以后千万小心,还是尽量不要用数组的第一个元素表示元素的个数了,因为这题里len[0]是可能被访问到的。改成cnt就完美AC了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
class _Tree{
private:
    struct Node{
        int l,r;
        char c;
    }tree[N*20];
public:
    int root[N],tree_cnt;
    void insert(int &x,int l,int r,int n,char c){
        tree[++tree_cnt]=tree[x];
        x=tree_cnt;
        if(l==r){tree[x].c=c;return;}
        int mid=l+r>>1;
        if(n<=mid)insert(tree[x].l,l,mid,n,c);
        else insert(tree[x].r,mid+1,r,n,c);
    }
    char query(int x,int l,int r,int n){
        if(l==r)return tree[x].c;
        int mid=l+r>>1;
        if(n<=mid)return query(tree[x].l,l,mid,n);
        else return query(tree[x].r,mid+1,r,n);
    }
}Tree;
int n,len[N],cnt;
int main(){
    freopen("type.in","r",stdin);
    freopen("type.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i){
        char op;cin>>op;
        if(op=='T'){
            char a;cin>>a;
            cnt++;
            len[cnt]=len[cnt-1]+1;
            Tree.root[cnt]=Tree.root[cnt-1];
            Tree.insert(Tree.root[cnt],1,N-10,len[cnt],a);
        }
        else{
            int a;cin>>a;
            if(op=='Q')cout<<Tree.query(Tree.root[cnt],1,N-10,a)<<'\n';
            else{
                cnt++;
                len[cnt]=len[cnt-a-1];
                Tree.root[cnt]=Tree.root[cnt-a-1];
            }
        }
    }
    return 0;
}