洛谷 P1383 codevs 3333 高级打字机

题目描述

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。

请为这种高级打字机设计一个程序，支持如下3种操作：

1.T x：在文章末尾打下一个小写字母x。(type操作)

2.U x：撤销最后的x次修改操作。（Undo操作）

（注意Query操作并不算修改操作）

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

说明

【数据范围】

对于40%的数据 n<=200;

对于100%的数据 n<=100000；保证Undo操作不会撤销Undo操作。

<高级挑战>

对于200%的数据 n<=100000；Undo操作可以撤销Undo操作。

<IOI挑战>

必须使用在线算法完成该题。

解题思路

　　主席树前置技能点——可持久化线段树。教学视频看这里。我已经搞不清主席树和可持久化线段树的关系了。常见的说法就是这两者是同一个东西，但是有些地方又说主席树专指解决区间第k大问题的可持久化线段树，听说当时是HJT方太96主席不会划分树，于是搞出了一个用可持久化权值线段树解决此问题的方法，比划分树、归并树更优秀，个人觉得这个说法更靠谱。

2019年7月27日09:10:55更新 Seter的博客，主席树历史

源代码

#include<stdio.h>

int n;

struct tree{

    int l,r;//左右儿子指针

    char cc;

}t[];

int root[]={},cnt=;

int len[]={};

void updata(int & now,int last,int l,int r,int pos,char c)

{

    now=cnt++;

    t[now].l=t[last].l;t[now].r=t[last].r;

    if(l==r)

    {

        t[now].cc=c;

        return;

    }

    int mid=l+r>>;

    if(pos>mid) updata(t[now].r,t[last].r,mid+,r,pos,c);

    else updata(t[now].l,t[last].l,l,mid,pos,c);

}

void query(int now,int l,int r,int pos)

{

    if(l==r)

    {

        printf("%c\n",t[now].cc);

        return;

    }

    int mid=l+r>>;

    if(pos>mid) query(t[now].r,mid+,r,pos);

    else query(t[now].l,l,mid,pos);

}

int main()

{

    scanf("%d",&n);

    int t=;

    for(int kkk=;kkk<=n;kkk++)

    {

        char mode[];

        scanf("%s",mode);

        if(mode[]=='T')

        {

            scanf("%s",mode);

            t++;

            len[t]=len[t-]+;

            updata(root[t],root[t-],,n,len[t],mode[]);

        }

        else if(mode[]=='U')

        {

            int x;

            scanf("%d",&x);

            root[t+]=root[t-x];

            len[t+]=len[t-x];

            t++;

        }

        else

        {

            int pos;

            scanf("%d",&pos);

            query(root[t],,n,pos);

        }

    }

    return ;

}

巴特西

洛谷 P1383 codevs 3333 高级打字机

题目描述

输入输出格式

输入输出样例

说明

解题思路

源代码

最新文章

热门文章