题目链接：传送门

Description

有一些盒子，盒子里可以放盒子，给出最初的盒子的状态，有两种操作，第一种是将某一个盒子移动到另一个盒子（如果操作不合法就直接忽略），第二种是查询某个盒子最外边的盒子的编号。

Solution

考虑先dfs一遍,第一次访问时在dfs序中新加一个x，子树访问完后再加一个x + N。 那么

TeX parse error: Undefined control sequence \[

即为盒内的状况。 我们考虑用Splay维护它，如果需要移动的话，直接将这个区间移动到目标位置后面即可，查询就直接查询最左端的点即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 5e5 + 10;

int N, M;
int e, Begin[Maxn], To[Maxn * 2], Next[Maxn * 2];
int Index, dfn[Maxn];
int f[Maxn], cnt, root;

struct tree
{
    int ch[2], fa;
};

namespace Splay
{
    tree Tree[Maxn];

    inline int judge_dir (int x)
    {
        return Tree[Tree[x].fa].ch[1] == x;
    }

    inline void Connect (int x, int f, int dir)
    {
        Tree[x].fa = f;
        Tree[f].ch[dir] = x;
    }

    inline void Rotate (int x)
    {
        int f = Tree[x].fa; 
        int dirx = judge_dir(x);
        int anc = Tree[f].fa;
        int dirf = judge_dir(f);
        Connect(Tree[x].ch[dirx ^ 1], f, dirx);
        Connect(f, x, (dirx ^ 1));
        Connect(x, anc, dirf);
    }

    inline void splay (int x, int y)
    {
        while (Tree[x].fa != y)
        {
            int f = Tree[x].fa;
            int dirx = judge_dir(x), dirf = judge_dir(f);
            if (Tree[f].fa == y) Rotate(x);
            else if (dirx == dirf) Rotate(f), Rotate(x);
            else Rotate(x), Rotate(x);
        }
    }

    inline void build (int &x, int l, int r, int fa)
    {
        if (l > r) return ;
        int mid = (l + r) >> 1;
        x = dfn[mid];
        Tree[x].ch[0] = Tree[x].ch[1] = 0;
        Tree[x].fa = fa;
        build (Tree[x].ch[0], l, mid - 1, x);
        build (Tree[x].ch[1], mid + 1, r, x);
    }

    inline int query (int x)
    {
        splay(x, 0);
        while (Tree[x].ch[0]) x = Tree[x].ch[0];
        return x;
    }

    inline void move (int x, int y)
    {
        if (x == y) return ;
        splay (x, 0), splay (x + N, x);
        int tmp = y;
        while (tmp)
        {
            if (Tree[x + N].ch[0] == tmp) return ;
            tmp = Tree[tmp].fa;
        }

        int a = Tree[x].ch[0], b = Tree[x + N].ch[1];
        Tree[x].ch[0] = Tree[x + N].ch[1] = Tree[a].fa = Tree[b].fa = 0;
        if (a && b)
        {
            while (Tree[b].ch[0]) b = Tree[b].ch[0];
            Tree[b].ch[0] = a;
            Tree[a].fa = b;
        }
        if (!y) return ;
        splay (y, 0);
        int now = Tree[y].ch[1];
        while (Tree[now].ch[0]) now = Tree[now].ch[0];
        splay (now, y);
        Tree[now].ch[0] = x;
        Tree[x].fa = now;
    }
}

inline void Init ()
{
    e = Index = root = 0;
    memset(Begin, 0, sizeof Begin);
    memset(f, 0, sizeof f);
    memset(Splay :: Tree, 0, sizeof Splay :: Tree);
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

inline void dfs (int x)
{
    dfn[++cnt] = x;
    for (int i = Begin[x]; i; i = Next[i])
        dfs(To[i]);
    dfn[++cnt] = x + N;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int fl = 0;
    while (~scanf("%d", &N))
    {
        if (fl) cout<<endl;
        else fl = 1;
        Init();
        for (int i = 1; i <= N; ++i)
        {
            int x;
            scanf("%d", &x);
            if (x)
                add_edge(x, i);
            else f[i] = 1;
        }
        for (int i = 1; i <= N; ++i)
        {
            if (!f[i]) continue;
            cnt = 0;
            dfs(i);
            Splay :: build (root, 1, cnt, 0);
        }
        scanf("%d", &M);

        while (M--)
        {
            int x, y;
            char s[10];
            scanf("%s", s);
            if (s[0] == 'M')
            {
                scanf("%d%d", &x, &y);
                Splay :: move (x, y);
            }
            else 
            {
                scanf("%d", &x);
                printf("%d\n", Splay :: query (x)), fflush(stdout);
            }
        }
    }
    return 0;
}