1. Description of the problem

Bessie is playing a game of squares numbered from 1 to N, each of which starts as a stack. Bessie performs P operations of two types: M X Y, which moves the stack containing X to the top of the stack containing Y as a whole; C X, query the number of squares under the X square. Please count the results of each Bessie operation.

II. Input and output

1. Input

First, act as a single integer P, indicating the number of operations. Lines 2 through P+1, each describing an operation.

2. Output

Statistics are output for each C operation.

3. Sample inputs and outputs

1. Input Sample

6

M 1 6

C 1

M 2 4

M 2 6

C 3

C 4

2. Output Sample

1

0

2

IV. Analysis

This problem includes two operations, moving and counting. This problem can be implemented by using and finding sets. When searching and merging sets, updating the number of blocks below the tree root is sufficient. Using and collecting can solve this problem quickly and efficiently.

5. Algorithmic Design

1. Initialization

Initialize each square's collection number to be its own.

2. Query or merge.

C X: Query the set number of X and output the number of squares under the X square.

d[i]: The number of squares under the i-th square.

Query the ancestor of X, unify the set number of the node passing through the path as the set number of the ancestor during the return process, and add the d value of the current node to the d value of its parent node.

M X Y: Merge X, Y collection numbers.

cnt[i]: The number of blocks in the I th stack of squares. First find the set a and B where X and Y are located, then change the set number of a to b, fa[a]=b, update d[a]=cnt[b],cnb[b]+=cnt[a].

6. Illustration

1. Initialization

fa[i]=i; // The set number to which the square I belongs

d[i]=0; // Number of squares under block I

cnt[i]=1; // Number of blocks on stack I

2. Consolidation

M 1 6: Move the stack containing 1 as a whole to the stack containing 6. First find ancestors 1 and 6, then change the set number of 1 to 6, fa[1]=6, update d[1]=cnt[6]=1,cnt[6]+=cnt[1]=2.

3. Query

C1: Query 1 how many squares are below. First query the set number of 1 to find ancestors. During the query process, add the D value of the current node to the D value of its parent node, d[1]=d[1]+d[6]=1.

4. Consolidation

M 2 4: Move the stack containing 2 as a whole to the stack containing 4. First find ancestors 2 and 4, then change the set number of 2 to 4, fa[2]=4, update d[2]=cnt[4]=1,cnt[4]=cnt[4]+cnt[2]=2.

5. Consolidation

M 2 6: Move the stack containing 2 as a whole to the stack containing 6. First find ancestors 4 and 6 of 2 and 6, then change the set number of 4 to 6, fa[4]=6, update d[4]=cnt[6]=2,cnt[6]=cnt[6]+cnt[4]=4.

6. Query

C 3: Query 3 how many squares are below. First query 3 collection numbers for 3, d[3]=0.

7. Query

C 4: Query 4 how many squares are below. First query the collection number of 4, modify the collection number of the current node to the collection number of its parent node during the query process, add the D value of the current node to the D value of its parent node, d[4]=d[4]+d[6]=2.

8. Query

C 2: Query 2 how many squares are below. Query the ancestor of 2 first, add D value of current node to D value of parent node during return, d[2]=d[2]+d[4]=3.

Seven Codes

package com.platform.modules.alg.alglib.poj1988;

public class Poj1988 {
    public String output = "";

    private final int N = 30010;
    int n;
    int fa[] = new int[N];
    int d[] = new int[N];
    int cnt[] = new int[N];

    void Init() {
        for (int i = 1; i < N; i++) {
            fa[i] = i;
            d[i] = 0;
            cnt[i] = 1;
        }
    }

    int Find(int x) {
        int fx = fa[x];
        if (x != fa[x]) {
            fa[x] = Find(fa[x]);
            d[x] += d[fx];
        }
        return fa[x];
    }

    void Union(int x, int y) {
        int a, b;
        a = Find(x);
        b = Find(y);
        fa[a] = b;
        d[a] = cnt[b];
        cnt[b] += cnt[a];
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        Init();
        for (int count = 0; count < n; count++) {
            String[] words = line[count + 1].split(" ");
            if (words[0].charAt(0) == 'C') {
                int i = Integer.parseInt(words[1]);
                Find(i);
                output += "" + d[i] + "\n";
            } else {
                int i = Integer.parseInt(words[1]);
                int j = Integer.parseInt(words[2]);
                Union(i, j);
            }
        }
        return output;
    }
}

8. Testing