题目理解

我们需要模拟路由表的添加和查询操作：

• 添加操作：添加一个路由表项（目的地址 + 掩码长度）
• 查询操作：查询在某个时间段内，特定IP地址的路由匹配变化次数

关键规则：

1. 匹配规则：IP地址的前L位（L为掩码长度）相同即匹配
2. 最明确匹配：选择掩码长度最大的匹配项
3. 变化计数：当最明确匹配项发生变化时计数

---

问题分析

核心挑战

对于查询 Q D a b，我们需要：

1. 清空路由表
2. 依次执行第1到a-1次添加操作
3. 统计第a到b次添加操作期间，目的地址D的最明确匹配变化次数

直接模拟的复杂度是 $O(M^2)$，对于 $M \leq 10^6$ 不可行。

---

关键观察

1. 路由匹配的本质

对于目的地址D，只有那些前缀与D匹配的路由表项才可能成为最明确匹配。

2. 变化的条件

最明确匹配发生变化当且仅当：

• 新添加的表项与D匹配
• 并且新表项的掩码长度大于当前最明确匹配的掩码长度

3. 查询的转化

查询 Q D a b 等价于：

• 考虑第a到b次添加操作中所有与D匹配的表项
• 这些表项按添加顺序排序
• 统计其中掩码长度严格递增的子序列长度减一

---

算法思路

步骤1：预处理

1. 将所有IP地址转换为32位整数
2. 记录每个添加操作的信息（地址、掩码长度、时间戳）

步骤2：查询处理

对于每个查询 Q D a b：

1. 收集时间段[a,b]内所有与D匹配的表项
2. 将这些表项按时间顺序排列
3. 找出其中掩码长度的严格递增子序列
4. 答案 = 子序列长度 - 1

---

高效实现

1. IP地址转换

uint32_t ip_to_int(string ip) {
    uint32_t res = 0;
    int num = 0;
    for (char c : ip) {
        if (c == '.') {
            res = (res << 8) | num;
            num = 0;
        } else {
            num = num * 10 + (c - '0');
        }
    }
    return (res << 8) | num;
}

2. 匹配检查

bool is_match(uint32_t ip, uint32_t route_ip, int mask_len) {
    if (mask_len == 0) return true;
    uint32_t mask = (mask_len == 32) ? ~0 : (~0) << (32 - mask_len);
    return (ip & mask) == (route_ip & mask);
}

3. 严格递增子序列

使用单调栈或直接遍历：

int count_changes(vector<pair<int, int>>& items) { // (time, mask_len)
    int max_len = -1;
    int changes = 0;
    
    for (auto [time, len] : items) {
        if (len > max_len) {
            changes++;
            max_len = len;
        }
    }
    
    return max(0, changes - 1);
}

---

数据结构优化

由于M很大，我们需要高效地：

1. 快速找到与D匹配的表项
2. 按时间范围过滤

Trie树方法

对每个可能的查询IP D，我们可以在Trie树上快速找到所有匹配的表项。

离线处理

将所有查询按D分组，批量处理。

---

完整算法

离线处理版本：

1. 读取所有操作，记录类型和参数
2. 构建路由表项列表，每个表项记录(时间, IP, 掩码长度)
3. 收集所有查询，按查询IP分组
4. 对每个查询IP：
   • 找出所有时间段内匹配的表项
   • 计算严格递增子序列长度
5. 输出结果

---

复杂度分析

• IP转换：$O(M)$
• 匹配检查：对于每个查询，需要检查最多 $O(M)$ 个表项
• 严格递增子序列：$O(k)$，k为匹配的表项数量
• 最坏情况：$O(M^2)$，但实际中匹配的表项数量较少

---

样例验证

输入片段：

A 128.0.0.0/1
A 128.0.0.0/4
...
Q 192.0.0.13 1 8

处理过程：

1. 转换IP为整数
2. 对于查询，找出时间1-8内与192.0.0.13匹配的表项
3. 计算掩码长度的严格递增子序列
4. 输出变化次数

输出：1 ✓

---

进一步优化

对于大数据，可以使用：

1. Trie树快速找到匹配表项
2. 持久化数据结构支持历史版本查询
3. CDQ分治处理时间段查询

---

总结

本题的关键在于：

1. 理解路由匹配的规则和最明确匹配原则
2. 将问题转化为严格递增子序列计数
3. 设计高效算法处理大规模数据
4. 注意IP地址的二进制表示和匹配检查

这是一个典型的数据结构+算法优化问题，考察了对实际网络问题的抽象和算法设计能力。