算法

(线性遍历) $O(T(N + G))$

1. 将所有的下标设置成从 0 开始。
2. 我们很容易就能求出来每个客人最后所在的位置。按照每个客人的走动方向，将客人分为两类，然后用两个哈希数组 pos_C 和 pos_A，记录下每个方向中，每个领事馆的在最后时刻的客人。
3. 接下来，我们仍然分为两类，求出每个方向中，领事馆最后一次遇到的客人。这一步可以通过遍历一次整个领事馆完成。
4. 不妨假设我们遍历顺时针方向，我们从任意一个最后时刻有客人的领事馆的位置开始，逆时针往回遍历。遍历途中，记录下来当前领事馆与之前最后有人的领事馆之间的距离，以及最后有人的领事馆的位置（从哈希表中获取，有了这个位置就可以找到这些人了）。如果距离大于了 M 则表示这个领事馆没有顺时针的人经过。
5. 逆时针方向走动的人同理。
6. 通过 4 和 5 两步，每个领事馆最后一次有哪些人经过就都知道了，然后就是比较两个方向的距离，取二者最小；二者相等则都取，更新每个客人的答案。

时间复杂度

• 每个领事馆和客人只遍历常数次，故每组测试数据仅需要 $O(N + G)$ 的时间。

空间复杂度

• 需要额外 $O(N + G)$ 的空间记录每个领事馆最后的客人编号，以及每个领事馆与最近有客人的领事馆的距离和位置，以及最终的答案数组。

C++ 代码

#include <cstdio>
#include <vector>

using namespace std;

const int N = 100010;
const int MAX = 100000000;

int T;
int n, g, m;

int main() {
    scanf("%d", &T);
    for (int test = 1; test <= T; test++) {
        scanf("%d%d%d", &n, &g, &m);
        vector<vector<int>> pos_C(n), pos_A(n);
        int start_C = -1, start_A = -1;
        for (int i = 0; i < g; i++) {
            int x;
            char s[10];
            scanf("%d%s", &x, s);
            if (s[0] == 'C') {
                int pos = ((x - 1 + m) % n + n) % n;
                pos_C[pos].push_back(i);
                if (start_C == -1)
                    start_C = pos;
            } else {
                int pos = ((x - 1 - m) % n + n) % n;
                pos_A[pos].push_back(i);
                if (start_A == -1)
                    start_A = pos;
            }
        }

        vector<pair<int, int>> r_C(n), r_A(n);

        for (int i = 0; i < n; i++)
            r_C[i] = r_A[i] = make_pair(MAX, -1);

        if (start_C != -1) {
            int i = start_C, dis = -1, last = -1;
            do {
                if (!pos_C[i].empty()) {
                    dis = -1;
                    last = i;
                }
                if (++dis <= m) {
                    r_C[i].first = dis;
                    r_C[i].second = last;
                }
                i = (i - 1 + n) % n;
            } while (i != start_C);
        }


        if (start_A != -1) {
            int i = start_A, dis = -1, last = -1;
            do {
                if (!pos_A[i].empty()) {
                    dis = -1;
                    last = i;
                }
                if (++dis <= m) {
                    r_A[i].first = dis;
                    r_A[i].second = last;
                }
                i = (i + 1) % n;
            } while (i != start_A);
        }

        vector<int> ans(g, 0);

        for (int i = 0; i < n; i++) {
            int min_dis = min(r_C[i].first, r_A[i].first);
            if (min_dis != MAX) {
                if (min_dis == r_C[i].first) {
                    for (auto &t : pos_C[r_C[i].second])
                        ans[t]++;
                }
                if (min_dis == r_A[i].first) {
                    for (auto &t : pos_A[r_A[i].second])
                        ans[t]++;
                }
            }
        }

        printf("Case #%d:", test);
        for (int i = 0; i < g; i++)
            printf(" %d", ans[i]);

        printf("\n");
    }
    return 0;
}