本文共 2923 字，大约阅读时间需要 9 分钟。

为了高效处理大量的M和C指令，我们采用并查集（Union-Find）数据结构来维护战舰的队列状态。每个战舰i维护以下信息：

• parent[i]：父节点。
• size[i]：集合大小。
• head[i]：集合的首节点。
• tail[i]：集合的末节点。
• count[i]：集合中的战舰数量。

操作步骤如下：

以下是实现代码：

#include 
   
    
#include 
    
     
using namespace std;
struct Node {
    int parent;
    int size;
    int head;
    int tail;
    int count;
};
int a[30001], b[30001], c[30001], t;
int find(int x, Node* nodes) {
    if (nodes[x].parent != x) {
        nodes[x].parent = find(nodes[x].parent, nodes);
    }
    return nodes[x].parent;
}
int union(int x, int y, int head_y, Node* nodes) {
    int root_x = find(x, nodes);
    int root_y = find(y, nodes);
    if (root_x == root_y) return 0;
    if (nodes[root_x].size < nodes[root_y].size) {
        swap(root_x, root_y);
    }
    nodes[root_y].parent = root_x;
    nodes[root_x].size += nodes[root_y].size;
    nodes[root_x].count += nodes[root_y].count;
    if (nodes[root_x].head == head_y) {
        nodes[root_x].head = nodes[root_y].head;
        nodes[root_x].tail = nodes[root_y].tail;
    } else {
        nodes[root_x].head = nodes[root_y].head;
        nodes[root_x].tail = nodes[root_y].tail;
    }
    return 1;
}
int main() {
    t = 0;
    read(t);
    Node nodes[30001];
    for (int i = 1; i <= 30000; ++i) {
        nodes[i].parent = i;
        nodes[i].size = 1;
        nodes[i].head = i;
        nodes[i].tail = i;
        nodes[i].count = 1;
    }
    for (int i = 0; i < t; ++i) {
        char op;
        int x, y;
        if (scanf("%c %d %d", &op, &x, &y) != 3) break;
        if (op == 'M') {
            int root_x = find(x, nodes);
            int root_y = find(y, nodes);
            if (root_x == root_y) continue;
            int merged = union(x, y, y, nodes);
        } else if (op == 'C') {
            int root_x = find(x, nodes);
            int root_y = find(y, nodes);
            if (root_x != root_y) {
                printf(-1);
            } else {
                int head_x = nodes[root_x].head;
                int tail_y = nodes[root_y].tail;
                if (head_x > tail_y) {
                    int distance = head_x - tail_y - 1;
                    if (distance == 0) {
                        printf(0);
                    } else {
                        printf(distance);
                    }
                } else {
                    int distance = tail_y - head_x + 1;
                    if (distance == 0) {
                        printf(0);
                    } else {
                        printf(distance);
                    }
                }
            }
        }
    }
    return 0;
}
    
   

步骤解释：

这种方法确保了每次操作的时间复杂度接近常数，能够高效处理大量输入。