P5768 [CQOI2016] 路由表

路由表查找是路由器在转发 IP 报文时的重要环节。通常路由表中的表项由目的地址、掩码、下一跳（Next Hop）地址和其他辅助信息组成。例如： | 目的地址 | 掩码长度 | 下一跳 | | :----------: | :----------: | :----------: | | 0.0.0.0 | /1 | 192.168.1.1 | | 128.0.0.0 | /1 | 192.168.1.1 | | 8.8.8.0 | /24 | 192.168.1.1 | | 8.8.8.8 | /32 | 192.168.1.253 | 当路由器收到一个 IP 报文时，会将报文中的目的 IP 地址与路由表中的表项逐条进行比较，选择匹配且**最明确**的表项，将报文转发给该表项中指定的下一跳。 匹配的过程是将报文中的目的地址和表项中的目的地址分别转为二进制串，再查看表项中的掩码长度，若掩码长度为 $x$ ，则将两个二进制串的前 $x$ 位进行比较，如果相同则认为匹配。 所谓**最明确**是指在有多个表项匹配时，掩码长度最大的表项。也可以理解为匹配的二进制位最多的项。 IP 地址转为二进制串的操作是把地址中 $4$ 个整数（一定在 $0$ 到 $255$ 的范围内）分别转为 $8$ 位二进制数，再顺序拼接起来，得到一个 位的二进制串。例如，$192.168.1.253$ 转为二进制串后为 $11000000 $ $10101000$ $00000001$ $11111101$。 我们以报文的目的地址为 $8.8.8.8$ 为例，说明其在上述路由表的匹配过程。 | 8.8.8.8 | 00001000 00001000 00001000 00001000 | | :----------: | :----------: | | 0.0.0.0/1 | $\color{red}{0}$0000000 00000000 00000000 00000000 | | 128.0.0.0/1 | $\color{red}{1}$0000000 00000000 00000000 00000000 | | 8.8.8.0/24 | $\color{red}{00001000}$ $\color{red}{00001000 }$ $\color{red}{00001000}$ 00000000 | | 8.8.8.8/32 | $\color{red}{00001000}$ $\color{red}{00001000 }$ $\color{red}{00001000}$ $\color{red}{00001000}$ | 上表将地址均转为二进制串，并用红色标记出待比较的位（由掩码长度决定）。将红色部分与报文中的目的地址比较，可知 $0.0.0.0/1$、$8.8.8.0/24$、$8.8.8.8/32$ 均能够匹配。路由器从中选取掩码长度最长（/32）的表项 $8.8.8.8/32$，将报文转发给其对应的下一跳地址 $192.168.1.253$。 在实际的核心路由器中，路由表通常较大（现在互联网的全局路由表已经接近 $60$ 万条记录），并且会随着新接入设备不断扩张。为了分析路由表变化对转发产生的影响，网络工程师想要知道一段时间内某个 IP 地址的路由表项选择发生了多少次变化（变化是指由于最明确匹配等因素选择了不同的表项，不考虑下一跳地址）。

无

无

对于一次查询的一种理解方式是：无视其它所有查询操作，只看添加操作。先清空路由表，然后执行第 $1$ 到 $a-1$ 次添加操作。之后再统计第 $a$ 到 $b$ 次添加操作过程中匹配改变的次数。 -------- 对于 $30\%$ 的数据，$M \le 10^3$； 对于 $100\%$ 的数据，$M \le 10^6$。 设一条表项的掩码长度为 $L$，数据保证将目的地址转为二进制串后，末尾的 $32-L$ 位均为 $0$。另外，保证不会重复添加目的地址和掩码长度都相同的表项。