POJ1988_ Cube Stacking

Cube Stacking

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 18973		Accepted: 6605
Case Time Limit: 1000MS

Description

Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.

Input

* Line 1: A single integer, P

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

Output

Print the output from each of the count operations in the same order as the input file.

Sample Input

6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4

Sample Output

1 0 2

Source

​ ​USACO 2004 U S Open​​

 

The main idea of the topic ：

Yes N(N<=30,000) Pile block , At first, every pile is a square . Block number 1 – N. There are two operations ：

• M x y ： Means to put a square x On the heap , Pick it up and fold it y On the pile .
• C x : Ask the square x How many squares are there below .

At most P (P<=100,000) Time . Yes, every time C operation , Output results .

 

Ideas ：

Use and look up sets , Add every two bricks , Let the brick below be the parent node , The brick on the top serves as the root node ; When two piles of bricks merge , Let the root node of the lower heap be the root node of the upper heap . Among them , except father Out of array , You also need two arrays sum( It is used to record how many bricks there are in each pile ),under Array ( Used to record the i How many bricks are there under a brick ), among sum The array is only updated when the heap is merged ,under The array should be updated when merging the heap and when compressing the path .

 

Code ：

Log in and copy

      
      

       
       # include<iostream>
       
       

       
       # include<stdio.h>
       
       

       
       # include<string.h>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       const 
       
       int 
       
       MAXN 
       
       = 
       
       30010;
       
       

       
       

       
       int 
       
       father[
       
       MAXN],
       
       sum[
       
       MAXN],
       
       under[
       
       MAXN];
       
       

       
       

       
       int 
       
       find(
       
       int 
       
       a)
       
       
{
       
       
    
       
       if(
       
       a
       
       ==
       
       father[
       
       a])
       
       
        
       
       return 
       
       a;
       
       

       
       
    
       
       int 
       
       t 
       
       = 
       
       find(
       
       father[
       
       a]);
       
       // find a The root node 
       
       
    
       
       under[
       
       a] 
       
       += 
       
       under[
       
       father[
       
       a]];
       
       // Find the path of the root node   to update a The number of bricks under the pile 
       
       
    
       
       father[
       
       a] 
       
       = 
       
       t;
       
       // Update root 
       
       

       
       
    
       
       return 
       
       father[
       
       a];
       
       
}
       
       

       
       void 
       
       Merge(
       
       int 
       
       a,
       
       int 
       
       b)
       
       

       
       // take a The stack is placed on b On the pile 
       
       
{
       
       
    
       
       int 
       
       pa 
       
       = 
       
       find(
       
       a);
       
       
    
       
       int 
       
       pb 
       
       = 
       
       find(
       
       b);
       
       
    
       
       if(
       
       pa
       
       ==
       
       pb)
       
       
        
       
       return;
       
       
    
       
       father[
       
       pa] 
       
       = 
       
       pb;
       
       // Update the root node of the upper heap to the root node of the lower heap 
       
       
    
       
       under[
       
       pa] 
       
       = 
       
       sum[
       
       pb];
       
       
    
       
       // The heap above increases b Number of heaps , here  =  and  +=  The effect is the same , Because the bottom of the top pile is a The root of the under The value is 0
       
       
    
       
       sum[
       
       pb] 
       
       += 
       
       sum[
       
       pa];
       
       
    
       
       //b The number of heaps plus a Number of heaps 
       
       
}
       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       int 
       
       P, 
       
       a, 
       
       b;
       
       
    
       
       char 
       
       cmd[
       
       20];
       
       
    
       
       for(
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       <= 
       
       MAXN; 
       
       i
       
       ++)
       
       
    {
       
       
        
       
       father[
       
       i] 
       
       = 
       
       i;
       
       
        
       
       under[
       
       i] 
       
       = 
       
       0;
       
       
        
       
       sum[
       
       i] 
       
       = 
       
       1;
       
       
    }
       
       
    
       
       while(
       
       ~scanf(
       
       "%d", 
       
       &
       
       P))
       
       
    {
       
       
        
       
       scanf(
       
       "%s",
       
       cmd);
       
       
        
       
       if(
       
       cmd[
       
       0]
       
       ==
       
       'M')
       
       
        {
       
       
            
       
       scanf(
       
       "%d%d", 
       
       &
       
       a, 
       
       &
       
       b);
       
       
            
       
       Merge(
       
       a,
       
       b);
       
       
        }
       
       
        
       
       else
       
       
        {
       
       
            
       
       scanf(
       
       "%d", 
       
       &
       
       a);
       
       
            
       
       find(
       
       a);
       
       
            
       
       printf(
       
       "%d\n",
       
       under[
       
       a]);
       
       
        }
       
       
    }
       
       

       
       

       
       
    
       
       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.
       
       
50.
       
       
51.
       
       
52.
       
       
53.
       
       
54.
       
       
55.
       
       
56.
       
       
57.
       
       
58.
       
       
59.
       
       
60.
       
       
61.