Comet OJ

C1261 [CQOI2016]路由表

内存限制：512 MB 时间限制：2000 ms

题目描述

路由表查找是路由器在转发 IP 报文时的重要环节。通常路由表中的表项由目的地址、掩码、下一跳（Next Hop）地址和其他辅助信息组成。例如：

image.png

当路由器收到一个 IP 报文时，会将报文中的目的 IP 地址与路由表中的表项逐条进行比较，选择匹配且最明确的表项，将报文转发给该表项中指定的下一跳。

匹配的过程是将报文中的目的地址和表项中的目的地址分别转为二进制串，再查看表项中的掩码长度，若掩码长度为 $x$，则将两个二进制串的前 $x$ 位进行比较，如果相同则认为匹配。

所谓最明确是指在有多个表项匹配时，掩码长度最大的表项。也可以理解为匹配的二进制位最多的项。

IP 地址转为二进制串的操作是把地址中 $4$ 个整数（一定在 $0$ 到 $255$ 的范围内）分别转为$8$位二进制数，再顺序拼接起来，得到一个 $32$ 位的二进制串。例如，192.168.1.253转为二进制串后为11000000 10101000 00000001 11111101。

我们以报文的目的地址为8.8.8.8为例，说明其在上述路由表的匹配过程。

00000.png

上表将地址均转为二进制串，并用红色标记出待比较的位（由掩码长度决定）。将红色部分与报文中的目的地址比较，可知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 地址的路由表项选择发生了多少次变化（变化是指由于最明确匹配等因素选择了不同的表项，不考虑下一跳地址）。

输入格式

第一行为整数 $M$，表示共有 $M$ 次操作。接下来 $M$ 行，每行描述一次操作。操作有两种：

A <D>/<L>

其中 $D $为一个 IP 地址，$L$ 为整数 $(1 \leq L \leq 32)$。添加一条表项至路由表，其目的地址为 $D$，掩码长度为 $L$。下一跳地址由于没有用到，故省略。

Q <D> <a> <b>

其中 $D$ 为一个 IP 地址，$a, b$ 为正整数 $(a \leq b)$。查询从第 $a$ 次至第 $b$ 次添加表项期间（含 $a, b$），目的地址 $D$ 的路由表项选择发生了多少次变化。保证查询时表中至少有 $b$ 个表项。

输出

包含若干行，每行仅有一个整数，依次对应每个查询操作。

样例

样例输入 1

47
A 128.0.0.0/1
A 128.0.0.0/4
A 100.200.20.0/23
A 241.170.96.0/20
A 74.128.0.0/17
A 193.24.0.0/14
A 128.0.0.0/19
A 128.0.0.0/13
A 128.0.0.0/5
A 128.0.0.0/11
A 128.0.0.0/12
A 192.0.0.0/7
Q 192.0.0.13 1 8
A 128.0.0.0/8
Q 128.0.0.15 1 8
A 74.0.0.0/8
A 96.0.0.0/4
A 193.24.0.0/23
A 100.192.0.0/11
A 128.0.0.0/18
A 128.0.0.0/20
Q 128.0.0.4 1 13
A 192.0.0.0/8
A 192.0.0.0/22
Q 128.0.0.7 1 14
A 128.0.0.0/23
A 74.128.0.0/14
A 128.0.0.0/14
A 128.0.0.0/25
A 74.128.0.0/12
Q 128.0.0.9 2 17
A 96.0.0.0/11
A 64.0.0.0/2
A 74.0.0.0/26
A 100.192.0.0/18
A 128.0.0.0/27
A 193.24.0.0/18
Q 128.0.0.3 4 21
Q 74.128.0.12 3 24
A 128.0.0.0/9
A 193.24.0.0/22
Q 128.0.0.7 4 24
A 192.0.0.0/10
Q 128.0.0.3 2 23
A 100.192.0.0/10
Q 241.170.96.2 1 26
Q 100.192.0.4 4 24

样例输出 1

1
3
3
3
2
2
1
3
4
2
2

提示

对于一次查询的一种理解方式是：无视其它所有查询操作，只看添加操作。先清空路由表，然后执行第 $1$ 到 $a - 1$ 次添加操作。之后再统计第 $a$ 到 $b$ 次添加操作过程中匹配改变的次数。

对于 $30\%$ 的数据，$M \leq 10^3$；

对于 $100\%$ 的数据，$M \leq 10^6$。

设一条表项的掩码长度为 $L$，数据保证将目的地址转为二进制串后，末尾的 $32 - L$ 位均为 $0$。另外，保证不会重复添加目的地址和掩码长度都相同的表项。