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

hdu2475 Box

2022-08-08 14:56: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
因为有根树 所以lct不可以换根 那怎么办 设f[x]表示在树的形态中真实的根 因为存在不合法的情况 所以先把子树切下来之后看x是否在y的上面 如果在 则再把它接回去 注意接回去的时候需要将 splay到根 否则位置将不对 如果该操作是合法的那么选择将x接到y上去 同时注意改变真实树中的f数组

      
      

       
       #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://blog.51cto.com/u_15744996/5555928

边栏推荐

猜你喜欢

随机推荐