当前位置：网站首页>hdu2475 Box

hdu2475 Box

2022-08-08 15:15:00 【51CTO】

http://www.elijahqi.win/2018/03/04/hdu2475-box/
Problem Description
There are N boxes on the ground, which are labeled by numbers from 1 to N. The boxes are magical, the size of each one can be enlarged or reduced arbitrarily.
Jack can perform the “MOVE x y” operation to the boxes: take out box x; if y = 0, put it on the ground; Otherwise, put it inside box y. All the boxes inside box x remain the same. It is possible that an operation is illegal, that is, if box y is contained (directly or indirectly) by box x, or if y is equal to x.
In the following picture, box 2 and 4 are directly inside box 6, box 3 is directly inside box 4, box 5 is directly inside box 1, box 1 and 6 are on the ground.

The picture below shows the state after Jack performs “MOVE 4 1”:

Then he performs “MOVE 3 0”, the state becomes:

During a sequence of MOVE operations, Jack wants to know the root box of a specified box. The root box of box x is defined as the most outside box which contains box x. In the last picture, the root box of box 5 is box 1, and box 3’s root box is itself.

Input
Input contains several test cases.
For each test case, the first line has an integer N (1 <= N <= 50000), representing the number of boxes.
Next line has N integers: a1, a2, a3, … , aN (0 <= ai <= N), describing the initial state of the boxes. If ai is 0, box i is on the ground, it is not contained by any box; Otherwise, box i is directly inside box ai. It is guaranteed that the input state is always correct (No loop exists).
Next line has an integer M (1 <= M <= 100000), representing the number of MOVE operations and queries.
On the next M lines, each line contains a MOVE operation or a query:
1. MOVE x y, 1 <= x <= N, 0 <= y <= N, which is described above. If an operation is illegal, just ignore it.
2. QUERY x, 1 <= x <= N, output the root box of box x.

Output
For each query, output the result on a single line. Use a blank line to separate each test case.

Sample Input
2 0 1 5 QUERY 1 QUERY 2 MOVE 2 0 MOVE 1 2 QUERY 1 6 0 6 4 6 1 0 4 MOVE 4 1 QUERY 3 MOVE 1 4 QUERY 1

Sample Output
1 1 2 1 1
because a tree with roots 所以lctRoots cannot be replaced 那怎么办设f[x]Represents the true root in the form of the tree Because there is an illegal situation So cut the subtree first and then look at itx是否在y的上面如果在 Then take it back Note that when you take it back, you need to put it back splay到根 Otherwise the location will be wrong If the operation is legal then select willx接到y上去 Also pay attention to changing in the real treef数组

       
       #include<cstdio>
       
#include<algorithm>
       
#define N 55000
       
using namespace std;
       
int fa[N],f[N],c[N][2],n,m;
       
inline bool isroot(int x){
       
    return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
       
}
       
inline void rotate(int x){
       
    int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
       
    if (!isroot(y)) c[z][c[z][1]==y]=x;
       
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
       
    c[y][l]=c[x][r];c[x][r]=y;
       
}
       
inline void splay(int x){
       
    while(!isroot(x)){
       
        int y=fa[x],z=fa[y];
       
        if (!isroot(y)){
       
            if (c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y);
       
        }rotate(x);
       
    }
       
}
       
inline void access(int x){
       
    for (int t=0;x;t=x,x=fa[x]) splay(x),c[x][1]=t;
       
}
       
inline int find(int x){
       
    access(x);splay(x);while(c[x][0]) x=c[x][0];return x;
       
}
       
inline void cut(int x){
       
    access(f[x]);splay(x);fa[x]=0;
       
}
       
int main(){
       
    freopen("hdu2475.in","r",stdin);
       
    bool flag=0;
       
    while(~scanf("%d",&n)){if (flag) puts("");else flag=1;
       
        for (int i=1;i<=n;++i) scanf("%d",&fa[i]),f[i]=fa[i],c[i][0]=c[i][1]=0;
       
        scanf("%d",&m);
       
        while(m--){
       
            char op[10];int x,y;scanf("%s%d",op,&x);
       
            if (op[0]=='Q') printf("%d\n",find(x));
       
            if (op[0]=='M'){
       
                scanf("%d",&y);cut(x);if (!y) continue;
       
                if (find(y)==x){splay(x);fa[x]=f[x];continue;}
       
                fa[x]=f[x]=y;
       
            }
       
        }
       
    }
       
    return 0;
       
}
      
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.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/220/202208081445530336.html

当前位置：网站首页>hdu2475 Box

hdu2475 Box

边栏推荐

猜你喜欢

随机推荐