【OI】操作树

操作数，一般用来做那些对数列进行添加、撤销操作的题。

假设一开始有一个空数列，有三个操作

（1）在数列后加一个数

（2）求数列中某位置的值

（3）撤销掉最后进行的若干次操作（1和3）

考虑建一棵树，1操作则为在当前节点下新加一个节点，2操作求数列k位置值，则为从根节点到当前节点k个节点的位置的节点

3操作撤销掉最后进行的k次操作则为回溯k个节点，同时记录回溯前的当前节点和回溯后的当前节点。

所以每次进行查询的时候，先从当前节点找父亲，一直找到根节点，记录节点个数，然后节点个数-k得到当前节点到要查询的节点的距离。

撤销操作的时候，父亲是1操作的节点就往上找父亲，父亲是3操作节点就跳到那个3操作回溯之前的那个“当前节点”

例如这道题:

总时间限制:: 10000ms
单个测试点时间限制:: 1000ms
内存限制:: 262144kB

描述

给一个空数列，有M次操作，每次操作是以下三种之一：

（1）在数列后加一个数

（2）求数列中某位置的值

（3）撤销掉最后进行的若干次操作（1和3）

输入

第一行一个正整数M。
接下来M行，每行开头是一个字符，若该字符为'A'，则表示一个加数操作，接下来一个整数x，表示在数列后加一个整数x；若该字符为'Q'，则表示一个询问操作，接下来一个整数x，表示求x位置的值；若该字符为'U'，则表示一个撤销操作，接下来一个整数x，表示撤销掉最后进行的若干次操作。

输出

对每一个询问操作单独输出一行，表示答案。

样例输入

样例输出

提示

1<=M<=10^5，输入保证合法，且所有整数可用带符号32位整型存储。

#include <cstdio>

#include <iostream>

const int MaxN = ;

int fa[MaxN];

//bool edge[MaxN][MaxN];

int n;

int V[MaxN];

int back[MaxN];

int main()

{

    scanf("%d",&n);

    int now_node;

    char XX;

    std::cin>>XX;

    int xx;

    scanf("%d",&xx);

    now_node = ;

    int node_cnt = ;

    V[node_cnt] = xx;

    for(int l = ; l <= n; l++){

        char X;

        std::cin>>X;

        if(X == 'A'){

            int nx;

            scanf("%d",&nx);

            V[++node_cnt] = nx;

            fa[node_cnt] = now_node;

            //edge[now_node][node_cnt] = 1;

            now_node = node_cnt;

        }

        else if(X == 'U'){

            int nx;

            scanf("%d",&nx);

            int last_node = now_node;

            for(int i = ; i <= nx; i++){

                if(!back[now_node])

                    now_node = fa[now_node];

                else

                    now_node = back[now_node];

            }

            back[now_node] = last_node;

        }

        else if(X == 'Q'){

            int nx;

            scanf("%d",&nx);

            int count = ;

            int tmp = now_node;

            while(){

                if(!fa[tmp]){

                    break;

                }

                tmp = fa[tmp];

                count++;

            }

            count = count - nx;

            tmp = now_node;

            for(int i = ; i <= count; i++){

                tmp = fa[tmp];

            }

            printf("%d\n",V[tmp]);

        }

    }

    return ;

}

巴特西

【OI】操作树

最新文章

热门文章