P2809. 告警抑制

解题思路

核心思路：抑制关系与哈希表

抑制和被抑制的关系，可以看作是一种依赖关系或配对关系。这种关系很自然会想到使用哈希表来构建。

由于同一个高级告警可能会抑制若干个低级告警，因此我们可以以高级告警作为 key，被抑制的低级告警所组成的列表作为 value，来构建哈希表。

遍历告警列表：两件事

在后续遍历整个告警列表的时候，我们要做两件事：

1. 判断当前遇到的这个告警是否已经被前面的其他更高优先级的告警抑制了 2. 这个告警如果能够抑制其他低优先级告警，那么这些低优先级告警即使在后面出现了也不应该输出

因此我们可以构建一个哈希集合，用来储存所有被抑制的不能输出的告警所构成的集合：

在遍历过程中，如果当前告警并没有位于 under_control_set 中，则它没有被抑制，可以输出：

同时，当前告警如果抑制了其他若干低等级告警，这些低等级告警都应该加入 under_control_set 中：

优化：避免重复操作

代码到这里基本已经完成了。但注意到还有一个可以优化的地方：同一个高级告警可能多次反复出现，但这个告警在第一次出现的时候就已经抑制了若干低级告警了，如果多次执行 for under_control in hash_table[string] 的循环，加入到 under_control_set 中的低级告警都是重复的无用功，会造成开销的浪费。

因此我们可以再构建一个 appear_set 哈希集合，用来储存出现过的告警所构成的集合。在执行 for under_control in hash_table[string] 的循环之前，多加一个判断：

复杂度分析

设抑制关系共 n 条，告警序列的长度为 m。

• 建表阶段：读入 n 条抑制关系，逐条往 hash_table 对应的列表里追加，O(n)。
• 遍历阶段：对告警序列中的每个告警做两次哈希集合查询（是否在 under_control_set 中、是否在 appear_set 中），均摊 O(1)，这部分共 O(m)。
• 内层的 for under_control in hash_table[string] 循环看似嵌套，但由于 appear_set 的保护，每种告警只在第一次出现时才展开它的抑制列表；而所有告警的抑制列表长度之和恰好等于抑制关系总数 n，所以这个内层循环在整个程序运行期间总共最多执行 n 次，属于均摊意义上的线性开销。
• 总时间 O(n + m)；空间为一个哈希表加两个哈希集合和答案列表，O(n + m)。

这也从复杂度角度解释了正文里 appear_set 这个优化的价值：如果没有它，同一个高频出现的告警每出现一次就要重扫一遍自己的抑制列表，最坏会退化到 O(n * m)；加上它之后，每条抑制关系只被处理一次。