官方题解｜ACGO社区

题目解析

考虑使用一种数据结构来高效维护用户 $A$ 和用户 $B$ 之间的关系。

使用 map<int, set<int>> user 来维护每位用户关注的所有其他用户：

user[A] 表示用户 $A$ 关注的所有用户的集合。

如果满足条件 user[A] 中存在 $B$ 且 user[B] 中存在 $A$ 则说明 $A$ 和 $B$ 目前属于互相关注的状态。

AC代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, q;
        cin >> n >> q;
        map<int, set<int>> fans;
        for (int i = 0; i < q; ++i) {
            int t, a, b;
            cin >> t >> a >> b;
            if (t == 1)
                user[a].insert(b);
            else if (t == 2)
                user[a].erase(b);
            else
                cout << (user[a].count(b) and user[b].count(a) ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

复杂度分析

对于每个操作时间复杂度为 $O(\log{N})$，总时间复杂度为 $O(Q\log{N})$。

---