信息学奥赛P3998题解：微博系统模拟与STL优化

1. 项目背景与需求解析

最近在准备信息学奥赛的同学应该都遇到过这样的场景：刷题列表里突然出现一道名为P3998 [SHOI2013]的发微博题目。这道来自上海省选的老题乍看平平无奇，但实际暗藏玄机。作为一道典型的模拟+数据结构题，它完美考察了选手对STL容器和时间复杂度的把控能力。

题目核心是模拟微博系统中的关注/取关操作和消息传播过程。系统需要处理三类事件：

1. 用户A关注用户B（建立关系）
2. 用户A取消关注用户B（解除关系）
3. 用户A发布微博（所有关注者接收）

特别需要注意的是，消息传播具有时效性——只有关注关系存在时发布的微博才能被看到。这就意味着我们需要精确记录每个操作的时间戳，这在常规模拟题中是比较少见的考点。

2. 数据结构设计与分析

2.1 核心容器选型

面对这类动态关系维护问题，我首先考虑的是如何高效存储和查询关注关系。经过多次尝试，最终确定以下数据结构方案：

cpp复制unordered_map<int, unordered_set<int>> following;  // 用户关注列表
unordered_map<int, vector<pair<int, int>>> tweets;  // 用户微博记录

选择unordered_map和unordered_set而非普通map/set主要基于两点考虑：

1. 用户ID范围不确定（题目未说明），哈希结构更节省空间
2. 关注操作不需要有序性，哈希查询O(1)复杂度更优

微博记录采用vector<pair<int,int>>存储，其中：

• first元素记录发布时间戳
• second元素记录当前有效关注数（关键优化点）

2.2 时间戳处理技巧

这是本题最容易踩坑的地方。直接暴力计算每个微博的传播范围会导致O(M^2)复杂度，在1e5数据量下必然超时。我的解决方案是：

cpp复制int timestamp = 0;  // 全局时间计数器

void postTweet(int user) {
    tweets[user].emplace_back(timestamp++, following[user].size());
}

记录发布时的关注者数量，这样在查询时可以快速计算有效传播量。这是