1. 题目背景与需求分析

P3998 [SHOI2013] 发微博是信息学奥林匹克竞赛（信奥）中的一道经典题目，主要考察选手对数据结构与算法的综合应用能力。题目要求模拟微博系统中的关注、取消关注和发布消息操作，并实时计算每个用户的可见消息数。

这道题的核心难点在于：

• 需要高效处理动态变化的关注关系
• 消息传播具有时效性（只有关注期间发布的消息才会计数）
• 数据规模可能达到10^5级别，必须保证O(1)或O(logn)时间复杂度的操作

2. 数据结构设计与选型

2.1 用户关系建模

最直接的思路是用邻接表存储关注关系：

cpp复制unordered_map<int, unordered_set<int>> following; // user -> 关注列表

但这样在取消关注时需要遍历所有消息，时间复杂度无法接受。

2.2 逆向思维：事件记录法

更优的方案是记录每个用户的状态变更事件：

cpp复制struct Event {
    int timestamp;
    int target;
    bool isFollow; // true关注 false取消
};
vector<Event> userEvents[MAX_USERS];

2.3 消息存储优化

对每条消息，只需记录：

cpp复制vector<pair<int, int>> messages; // (发布者, 时间戳)

3. 核心算法实现

3.1 关注/取消关注处理

cpp复制void follow(int u, int v) {
    events[u].push_back({currentTime, v, true});
    events[v].push_back({currentTime, u, true});
    currentTime++;
}

void unfollow(int u, int v) {
    events[u].push_back({currentTime, v, false});
    events[v].push_back({currentTime, u, false});
    currentTime++;
}