ID: 2881

传统题

1000ms

256MiB

尝试: 0

已通过: 0

难度: (无)

上传者:

biodoteacher

标签>

单调栈

Description

路由表查找是路由器在转发IP报文时的重要环节。通常路由表中的表项由目的地址、掩码、下一

跳（Next Hop）地址和其他辅助信息组成。例如：

当路由器收到一个IP报文时，会将报文中的目的IP地址与路由表中的表项逐条进行比较，选

择匹配且最明确的表项，将报文转发给该表项中指定的下一跳。

匹配的过程是将报文中的目的地址和表项中的目的地址分别转为二进制串，再查看表项中的掩

码长度，若掩码长度为x，则将两个二进制串的前x位进行比较，如果相同则认为匹配。

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

位最多的项。

IP地址转为二进制串的操作是把地址中4个整数（一定在y到255的范围内）分别转为8位

二进制数，再顺序拼接起来，得到一个32位的二进制串。例如，192.168.1.253转为二进制串后为

11000000 10101000 00000001 11111101

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

上表将地址均转为二进制串，并用红色标记出待比较的位（由掩码长度决定）。将红色部分与

报文中的目的地址比较，可知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地址的路由表项选择发生了多少次变化（变化是指由于最明确匹配等因素选择

了不同的表项，不考虑下一跳地址）。

Format

Input

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

A D/L

其中.为一个IP地址，G为整数（1≤L≤32）。添加一条表项至路由表，其目的地址为

D掩码长度为L。下一跳地址由于没有用到，故省略。

Q D a b

其中D为一个IP地址，a,b为正整数（a≤b）。查询从第a次至第b次添加表项期间（含

a、b），目的地址D的路由表项选择发生了多少次变化。保证查询时表中至少有b个表项。

N<=10^6数据保证不会重复添加目的地址和掩码长度都相同的表项。

Output

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

Samples

1000
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
A 74.0.0.0/21
A 192.0.0.0/6
A 128.0.0.0/24
Q 74.128.0.5 1 24
Q 74.128.0.6 4 26
A 192.0.0.0/13
A 100.192.0.0/27
Q 128.0.0.6 2 29
A 100.128.0.0/9
Q 74.0.0.13 3 31
A 100.0.0.0/7
A 96.0.0.0/16
A 128.0.0.0/16
A 192.0.0.0/27
A 240.0.0.0/6
Q 100.0.0.1 4 33
A 128.0.0.0/3
Q 128.0.0.6 6 36
A 193.24.0.0/17
Q 96.0.0.15 3 31
A 3.220.186.0/26
A 192.0.0.0/18
Q 128.0.0.13 1 32
A 74.0.0.0/9
A 232.0.0.0/5
Q 128.0.0.11 2 34
A 192.0.0.0/17
A 100.128.0.0/18
Q 3.220.186.4 6 36
A 64.0.0.0/28
Q 100.0.0.5 7 39
A 96.0.0.0/13
A 192.0.0.0/9
Q 128.0.0.3 1 39
A 128.0.0.0/28
A 100.0.0.0/6
A 193.24.0.0/26
A 192.0.0.0/28
Q 128.0.0.0 4 46
A 96.0.0.0/3
Q 128.0.0.10 2 42
Q 100.0.0.5 2 46
A 96.0.0.0/22
A 100.192.0.0/22
A 128.0.0.0/26
A 192.0.0.0/16
A 128.0.0.0/15
Q 64.0.0.0 6 48
Q 96.0.0.0 1 49
A 192.0.0.0/20
A 100.0.0.0/26
A 193.24.0.0/25
Q 100.128.0.6 6 50
Q 192.0.0.2 2 46
Q 128.0.0.2 5 51
A 0.0.0.0/1
A 100.192.0.0/24
A 192.0.0.0/4
Q 74.128.0.11 1 50
A 100.128.0.0/20
A 192.0.0.0/11
A 74.0.0.0/27
Q 193.24.0.12 9 52
A 163.214.12.64/26
A 232.0.0.0/13
A 100.128.0.0/16
A 192.0.0.0/3
A 100.0.0.0/8
A 128.0.0.0/10
Q 64.0.0.5 2 56
A 74.0.0.0/15
A 128.0.0.0/17
Q 193.24.0.14 8 61
A 0.0.0.0/6
A 74.0.0.0/13
Q 100.192.0.6 9 63
A 100.192.0.0/14
Q 192.0.0.6 5 56
Q 193.24.0.0 6 61
A 96.0.0.0/28
A 128.0.0.0/21
A 193.24.0.0/19
A 192.0.0.0/26
Q 74.0.0.8 11 68
A 100.0.0.0/21
A 100.192.0.0/29
Q 128.0.0.4 7 67
A 193.24.0.0/13
Q 128.0.0.4 9 62
Q 128.0.0.4 11 67
A 192.0.0.0/12
A 100.192.0.0/20
Q 193.24.0.12 4 72
Q 96.0.0.10 5 63
Q 241.170.96.10 1 71
Q 128.0.0.3 12 68
Q 3.220.186.2 6 65
Q 192.0.0.11 8 65
A 240.0.0.0/14
A 128.0.0.0/22
A 193.24.0.0/21
A 64.0.0.0/5
A 0.0.0.0/5
Q 192.0.0.10 5 75
Q 128.0.0.3 12 68
A 193.24.0.0/16
A 8.0.0.0/5
A 96.0.0.0/5
A 128.0.0.0/29
Q 74.128.0.8 12 78
A 232.0.0.0/8
Q 74.128.0.13 10 67
A 100.128.0.0/21
A 100.128.0.0/22
A 192.0.0.0/29
A 192.0.0.0/5
A 0.0.0.0/18
Q 193.24.0.14 6 73
A 192.0.0.0/23
Q 100.0.0.3 13 82
A 100.192.0.0/21
A 96.0.0.0/14
A 240.0.0.0/11
A 8.0.0.0/26
A 0.0.0.0/4
A 100.200.0.0/19
Q 192.0.0.12 6 78
A 0.0.0.0/3
A 8.0.0.0/11
A 0.0.0.0/24
Q 128.0.0.0 2 77
A 100.0.0.0/11
Q 232.0.0.14 7 84
Q 74.0.0.1 15 90
A 240.0.0.0/25
A 100.128.0.0/13
Q 8.0.0.11 3 84
A 100.128.0.0/12
A 8.0.0.0/18
A 128.0.0.0/2
A 193.24.0.0/20
Q 74.0.0.12 2 91
Q 100.192.0.9 3 90
A 0.0.0.0/29
A 0.0.0.0/10
Q 232.0.0.12 15 83
Q 192.0.0.5 15 86
A 193.0.0.0/9
A 240.0.0.0/20
Q 0.0.0.2 16 98
Q 128.0.0.6 16 88
A 100.192.0.0/12
Q 192.0.0.3 7 99
A 8.0.0.0/22
Q 192.0.0.6 16 86
Q 96.0.0.0 15 90
A 0.0.0.0/21
A 192.0.0.0/2
Q 74.0.0.9 10 86
A 100.128.0.0/25
Q 100.192.0.14 5 92
Q 100.200.20.13 17 93
Q 100.192.0.3 16 88
Q 100.128.0.2 13 92
Q 8.0.0.0 5 97
A 160.0.0.0/5
Q 100.0.0.8 15 96
A 0.0.0.0/14
A 100.192.0.0/26
Q 128.0.0.8 8 95
Q 0.0.0.15 17 98
A 8.0.0.0/16
A 100.192.0.0/13
Q 128.0.0.12 16 101
Q 128.0.0.4 5 91
A 96.0.0.0/24
Q 193.24.0.13 1 102
Q 240.0.0.5 10 108
A 100.128.0.0/15
Q 193.0.0.10 2 107
A 100.128.0.0/27
A 3.192.0.0/10
A 224.0.0.0/3
Q 0.0.0.7 10 105
Q 100.128.0.1 15 93
Q 193.24.0.2 7 96
Q 100.200.20.3 2 94
A 74.0.0.0/16
A 193.0.0.0/23
Q 193.24.0.2 2 96
Q 128.0.0.6 12 101
A 213.251.112.0/22
A 241.160.0.0/12
A 96.0.0.0/17
A 100.0.0.0/14
A 96.0.0.0/7
Q 192.0.0.8 7 113
Q 96.0.0.12 2 111
A 100.128.0.0/17
A 193.0.0.0/13
Q 96.0.0.1 4 100
Q 100.192.0.13 10 103
A 192.0.0.0/15
Q 193.24.0.4 2 103
A 100.0.0.0/12
A 100.128.0.0/29
Q 241.170.96.7 13 105
A 100.128.0.0/19
Q 100.128.0.1 16 104
Q 192.0.0.13 5 102
A 192.0.0.0/30
Q 96.0.0.2 4 118
A 74.0.0.0/29
A 100.192.0.0/15
Q 193.24.0.12 10 107
A 96.0.0.0/19
A 74.128.0.0/10
A 0.0.0.0/20
A 74.0.0.0/7
A 193.0.0.0/20
Q 100.0.0.2 17 117
A 96.0.0.0/29
A 193.0.0.0/14
Q 100.192.0.7 11 109
A 100.0.0.0/29
Q 74.0.0.14 14 127
A 96.0.0.0/20
Q 100.128.0.7 19 126
Q 163.214.12.69 1 123
Q 128.0.0.1 10 122
A 96.0.0.0/25
A 74.0.0.0/14
A 192.0.0.0/21
Q 100.0.0.3 9 129
Q 192.0.0.8 20 124
Q 74.0.0.4 5 120
A 74.128.0.0/19
Q 0.0.0.1 19 121
Q 241.160.0.1 15 114
A 224.0.0.0/20
Q 192.0.0.5 11 127
Q 232.0.0.10 20 112
A 192.0.0.0/25
Q 100.192.0.1 10 115
A 100.0.0.0/27
A 100.0.0.0/19
A 64.0.0.0/13
A 8.0.0.0/14
Q 100.0.0.14 7 133
A 74.0.0.0/11
A 100.128.0.0/23
A 163.214.12.0/24
A 0.0.0.0/8
A 0.0.0.0/7
A 72.0.0.0/6
A 193.24.0.0/29
Q 100.128.0.1 7 131
A 193.0.0.0/28
A 100.128.0.0/14
A 232.0.0.0/19
Q 100.128.0.10 17 122
A 128.0.0.0/6
Q 192.0.0.13 22 138
A 96.0.0.0/9
Q 128.0.0.13 9 143
Q 128.0.0.5 13 139
A 0.0.0.0/13
A 193.88.0.0/16
A 0.0.0.0/19
A 100.192.0.0/23
A 213.240.0.0/12
A 100.0.0.0/23
A 72.0.0.0/5
A 3.192.0.0/18
A 74.0.0.0/22
A 100.192.0.0/25
Q 96.0.0.9 20 136
Q 192.0.0.7 15 132
A 160.0.0.0/25
Q 0.0.0.2 6 130
Q 100.128.0.12 24 143
Q 192.0.0.4 20 152
Q 100.0.0.14 25 130
A 232.0.0.0/21
A 0.0.0.0/28
A 72.0.0.0/13
Q 128.0.0.2 6 134
Q 100.192.0.5 20 149
Q 192.0.0.12 26 131
Q 193.0.0.8 11 146
Q 74.128.0.4 17 132
A 0.0.0.0/25
A 0.0.0.0/15
Q 100.128.0.11 23 145
A 16.0.0.0/5
Q 192.0.0.11 19 134
A 232.0.0.0/29
A 74.128.0.0/13
A 232.0.0.0/26
A 241.160.0.0/25
A 96.0.0.0/12
A 74.0.0.0/12
A 162.0.0.0/7
A 100.192.0.0/30
A 193.24.0.0/30
A 64.0.0.0/3
A 193.0.0.0/11
A 155.49.0.0/16
Q 128.0.0.4 18 159
Q 193.24.0.2 10 143
A 240.0.0.0/12
Q 100.200.0.5 4 148
A 74.128.0.0/24
A 193.16.0.0/12
Q 74.0.0.4 3 143
Q 128.0.0.0 18 157
A 0.0.0.0/9
A 72.0.0.0/9
A 120.0.0.0/6
A 0.0.0.0/12
A 100.0.0.0/16
A 0.0.0.0/22
Q 192.0.0.11 29 155
Q 100.0.0.2 3 152
Q 193.24.0.2 21 147
Q 74.0.0.6 4 154
A 96.0.0.0/6
A 232.0.0.0/24
A 128.0.0.0/30
A 128.0.0.0/7
A 74.128.0.0/9
Q 128.0.0.10 27 153
A 74.0.0.0/28
Q 100.192.0.5 6 171
Q 100.0.0.8 10 151
A 16.0.0.0/27
A 193.0.0.0/16
Q 72.0.0.0 29 167
Q 240.0.0.3 16 163
A 224.0.0.0/24
A 0.0.0.0/2
A 100.128.0.0/26
A 100.192.0.0/19
A 3.220.186.0/28
Q 193.24.0.0 20 158
A 193.24.0.0/15
Q 72.0.0.1 21 159
Q 16.0.0.10 11 156
A 240.0.0.0/4
A 72.0.0.0/16
A 16.0.0.0/24
Q 3.192.0.3 6 161
A 232.0.0.0/15
A 8.0.0.0/25
A 8.0.0.0/6
Q 224.0.0.5 10 186
Q 96.0.0.4 31 169
A 16.0.0.0/26
Q 100.0.0.11 30 186
A 213.240.0.0/27
A 96.0.0.0/21
Q 74.128.0.13 24 182
Q 100.192.0.5 21 182
A 193.0.0.0/10
Q 193.0.0.0 22 166
A 74.0.0.0/23
Q 232.0.0.0 7 185
A 179.11.167.64/29
Q 192.0.0.0 24 163
A 193.0.0.0/25
Q 128.0.0.13 16 193
Q 72.0.0.9 3 174
Q 100.192.0.0 5 173
A 224.0.0.0/5
Q 96.0.0.15 29 170
Q 16.0.0.5 2 186
Q 193.24.0.3 14 184
Q 100.128.0.0 19 188
Q 74.0.0.12 10 191
A 162.0.0.0/22
Q 192.0.0.12 2 188
A 241.160.0.0/21
Q 193.24.0.2 22 196
A 100.0.0.0/13
A 241.170.96.0/27
A 100.192.0.0/28
A 179.11.0.0/16
A 100.200.20.0/30
A 193.0.0.0/24
A 224.0.0.0/4
Q 232.0.0.5 21 197
Q 128.0.0.1 9 178
A 3.220.160.0/19
Q 74.0.0.4 29 180
A 0.0.0.0/17
Q 192.0.0.5 19 172
A 3.192.0.0/15
A 72.0.0.0/14
A 160.0.0.0/6
Q 128.0.0.12 11 184
A 224.0.0.0/22
A 179.11.0.0/18
Q 192.0.0.14 26 181
A 213.0.0.0/8
A 178.0.0.0/7
A 240.0.0.0/10
A 100.0.0.0/10
Q 128.0.0.2 28 207
Q 100.128.0.8 9 203
A 74.128.0.0/11
Q 100.128.0.9 19 195
A 74.128.0.0/18
A 240.0.0.0/7
Q 240.0.0.2 35 198
A 232.0.0.0/30
A 74.0.0.0/17
Q 8.0.0.11 18 199
Q 224.0.0.2 19 194
Q 100.192.0.5 26 202
A 72.0.0.0/27
A 72.0.0.0/11
Q 193.0.0.7 18 187
A 74.0.0.0/19
Q 100.128.0.14 3 203
A 192.0.0.0/24
A 240.0.0.0/30
A 240.0.0.0/24
A 100.0.0.0/17
A 96.0.0.0/8
A 224.0.0.0/8
Q 100.192.0.1 19 198
Q 8.0.0.8 32 207
Q 74.0.0.15 10 205
Q 0.0.0.4 29 197
A 247.48.0.0/12
A 162.0.0.0/27
A 240.0.0.0/23
Q 96.0.0.11 4 195
A 72.0.0.0/20
Q 74.0.0.12 10 202
A 74.128.0.0/28
A 100.0.0.0/9
Q 100.0.0.2 3 223
A 96.0.0.0/30
Q 72.0.0.12 36 216
Q 96.0.0.9 11 192
A 16.0.0.0/20
A 64.0.0.0/6
Q 213.240.0.1 11 210
A 100.128.0.0/10
A 100.0.0.0/25
Q 96.0.0.10 37 200
A 120.0.0.0/22
A 224.0.0.0/16
Q 74.0.0.11 35 212
A 224.0.0.0/29
A 232.0.0.0/14
A 0.0.0.0/16
Q 16.0.0.2 21 211
Q 0.0.0.14 25 200
A 74.0.0.0/30
A 232.0.0.0/16
Q 128.0.0.7 15 215
Q 96.0.0.6 24 217
A 16.0.0.0/25
A 192.0.0.0/19
A 20.30.128.0/20
A 100.0.0.0/31
A 179.11.0.0/29
Q 179.11.0.6 1 221
A 224.0.0.0/13
Q 213.240.0.1 1 215
Q 74.0.0.1 27 230
Q 192.0.0.10 3 236
A 100.192.0.0/31
A 100.0.0.0/24
A 224.0.0.0/17
Q 72.0.0.7 23 208
Q 100.192.0.5 10 208
A 74.0.0.0/31
Q 74.0.0.6 1 224
Q 232.0.0.10 6 211
A 74.128.0.0/20
A 72.0.0.0/17
A 74.128.0.0/22
A 224.0.0.0/7
A 191.11.64.0/18
A 224.0.0.0/12
Q 224.0.0.13 12 229
A 8.0.0.0/29
A 100.192.0.0/16
Q 193.16.0.2 35 224
Q 0.0.0.15 13 241
A 16.0.0.0/10
A 241.160.0.0/13
Q 100.0.0.1 28 211
A 72.0.0.0/10
A 118.101.156.224/27
A 100.200.0.0/18
Q 100.0.0.7 18 224
A 232.0.0.0/23
Q 100.0.0.11 34 229
Q 8.0.0.13 27 243
A 20.30.128.0/31
A 213.0.0.0/27
A 8.0.0.0/24
Q 100.128.0.5 29 218
A 128.0.0.0/31
A 3.220.160.0/28
A 3.192.0.0/17
A 213.0.0.0/12
A 240.0.0.0/18
Q 100.192.0.0 27 220
Q 96.0.0.9 30 251
Q 100.128.0.11 20 224
A 74.0.0.0/18
A 62.188.0.0/15
A 162.0.0.0/28
Q 128.0.0.9 14 240
A 193.0.0.0/19
A 96.0.0.0/31
A 0.0.0.0/31
Q 128.0.0.6 42 252
A 232.0.0.0/7
A 0.0.0.0/11
Q 192.0.0.0 29 254
A 64.0.0.0/25
A 96.0.0.0/27
Q 193.24.0.0 23 226
A 100.128.0.0/11
Q 193.24.0.13 44 232
A 241.160.0.0/19
Q 0.0.0.9 15 223
A 8.0.0.0/12
Q 74.0.0.7 13 240
A 100.192.0.0/17
A 191.0.0.0/12
A 96.0.0.0/18
A 100.0.0.0/30
Q 8.0.0.10 13 238
A 213.0.0.0/26
A 8.0.0.0/9
A 3.0.0.0/8
A 118.101.128.0/18
Q 74.128.0.14 24 272
A 0.0.0.0/26
A 241.170.96.0/30
Q 74.128.0.8 18 232
Q 20.30.128.6 6 270
A 191.0.0.0/28
A 213.0.0.0/9
A 64.0.0.0/20
Q 179.11.0.12 12 260
Q 0.0.0.11 1 262
Q 120.0.0.6 35 251
Q 8.0.0.6 3 267
A 64.0.0.0/16
Q 96.0.0.15 4 258
A 16.0.0.0/4
A 179.11.0.0/20
A 160.0.0.0/18
A 74.0.0.0/24
Q 192.0.0.8 10 243
A 224.0.0.0/21
A 8.0.0.0/19
Q 128.0.0.11 13 275
A 72.0.0.0/19
Q 224.0.0.11 12 273
A 240.0.0.0/15
A 0.0.0.0/27
Q 96.0.0.13 12 262
A 193.24.0.0/27
A 192.0.0.0/31
A 3.208.0.0/12
A 179.0.0.0/8
Q 240.0.0.2 32 274
A 64.0.0.0/18
Q 240.0.0.6 3 282
A 232.0.0.0/6
A 247.48.0.0/15
A 193.0.0.0/8
A 160.0.0.0/9
A 16.0.0.0/28
Q 128.0.0.8 7 272
Q 128.0.0.11 39 290
Q 100.0.0.2 38 280
Q 224.0.0.0 8 249
Q 96.0.0.6 27 284
A 20.0.0.0/9
A 100.128.0.0/30
A 224.0.0.0/15
Q 128.0.0.5 7 259
Q 74.0.0.14 2 261
Q 100.128.0.14 25 250
Q 240.0.0.13 41 286
Q 160.0.0.2 15 293
A 8.0.0.0/23
Q 193.0.0.14 43 294
A 16.0.0.0/17
A 192.0.0.0/14
A 74.0.0.0/10
A 74.0.0.0/20
A 241.160.0.0/27
Q 100.0.0.14 6 278
Q 162.0.0.14 5 264
Q 74.128.0.3 14 258
Q 128.0.0.3 38 274
A 72.0.0.0/22
A 122.38.0.0/15
A 240.0.0.0/29
Q 0.0.0.14 35 291
Q 213.0.0.13 32 280
A 213.0.0.0/17
A 232.0.0.0/22
A 232.0.0.0/17
Q 74.0.0.4 18 256
A 20.0.0.0/20
Q 16.0.0.2 13 280
Q 100.128.0.7 45 291
A 94.3.0.0/16
Q 240.0.0.10 41 268
A 163.208.0.0/12
A 95.0.0.0/9
Q 224.0.0.1 6 270
A 232.0.0.0/9
Q 72.0.0.3 30 274
A 160.0.0.0/16
A 191.11.0.0/16
A 240.0.0.0/28
A 163.214.0.0/16
A 72.217.252.176/29
A 241.160.0.0/16
Q 192.0.0.4 38 282
A 20.0.0.0/12
A 120.0.0.0/25
Q 0.0.0.6 32 279
Q 100.192.0.1 48 299
A 240.0.0.0/19
Q 128.0.0.12 37 270
A 74.128.0.0/26
A 232.0.0.0/11
A 96.0.0.0/15
Q 192.0.0.15 12 289
A 160.0.0.0/28
A 179.0.0.0/27
A 74.128.0.0/21
A 8.0.0.0/21
Q 74.128.0.6 38 283
Q 128.0.0.10 21 271
A 240.0.0.0/22
Q 100.192.0.11 36 277
A 8.0.0.0/30
Q 162.0.0.12 2 289
Q 100.192.0.7 21 271
Q 128.0.0.9 25 308
A 64.0.0.0/8
Q 3.208.0.9 43 291
Q 178.0.0.0 30 307
Q 72.0.0.10 11 298
A 72.0.0.0/8
Q 128.0.0.14 15 295
A 0.0.0.0/23
A 151.48.12.96/27
A 191.0.0.0/30
Q 74.128.0.14 19 320
Q 74.0.0.7 53 297
A 100.0.0.0/28
A 179.11.167.64/31
A 8.0.0.0/8
A 3.128.0.0/9
A 193.88.0.0/14
Q 120.0.0.1 11 325
A 120.0.0.0/13
Q 94.3.0.8 5 318
Q 100.128.0.8 32 312
Q 240.0.0.5 42 311
Q 162.0.0.14 50 300
A 240.0.0.0/26
A 160.0.0.0/3
A 213.248.0.0/13
Q 16.0.0.6 54 297
A 64.0.0.0/4
Q 100.192.0.8 26 331
A 224.0.0.0/9
Q 100.192.0.0 5 301
A 120.0.0.0/17
A 103.119.244.96/28
A 240.0.0.0/8
Q 232.0.0.1 12 327
Q 96.0.0.8 28 306
Q 224.0.0.13 53 289
A 160.0.0.0/17
A 241.160.0.0/24
A 64.0.0.0/26
A 160.0.0.0/4
A 100.200.0.0/13
Q 179.11.0.4 12 307
Q 193.24.0.4 10 308
A 96.0.0.0/23
A 16.0.0.0/14
Q 100.192.0.4 46 331
A 8.0.0.0/13
A 163.208.0.0/31
A 178.0.0.0/30
A 160.0.0.0/14
Q 191.11.64.4 35 315
Q 224.0.0.15 33 331
Q 192.0.0.9 27 300
Q 193.24.0.15 49 324
A 151.48.8.0/21
A 224.0.0.0/18
A 213.128.0.0/9
A 191.0.0.0/23
A 74.128.0.0/16
A 120.0.0.0/10
Q 193.24.0.1 15 315
Q 8.0.0.11 3 336
Q 192.0.0.8 17 306
Q 192.0.0.12 13 329
Q 192.0.0.0 52 344
A 151.48.12.0/23
A 3.192.0.0/11
Q 240.0.0.10 20 329
A 8.0.0.0/27
A 120.0.0.0/31
A 162.0.0.0/26
A 64.0.0.0/29
Q 100.0.0.15 38 304
A 118.101.128.0/28
A 120.0.0.0/28
A 179.11.0.0/30
A 240.0.0.0/5
A 224.0.0.0/31
A 247.48.0.0/29
A 240.0.0.0/27
A 20.30.128.0/28
A 224.0.0.0/11
A 213.0.0.0/21
Q 72.0.0.14 11 340
A 134.161.96.0/21
A 193.88.0.0/31
A 160.0.0.0/20
Q 240.0.0.14 44 338
A 160.0.0.0/21
Q 74.128.0.13 51 325
Q 0.0.0.8 40 360
Q 0.0.0.0 6 346
Q 74.0.0.2 28 337
Q 0.0.0.1 40 312
A 213.0.0.0/28
A 193.0.0.0/21
Q 179.11.167.78 27 309
A 160.0.0.0/22
A 179.11.0.0/26
A 162.0.0.0/13
A 3.192.0.0/16
Q 128.0.0.6 18 319
A 191.0.0.0/11
A 191.0.0.0/24
Q 64.0.0.4 18 319
A 215.172.0.0/14
Q 0.0.0.6 1 330
A 112.0.0.0/4
A 224.0.0.0/27
A 162.0.0.0/21
Q 162.0.0.15 9 356
A 240.0.0.0/9
A 224.0.0.0/28
A 64.0.0.0/23
A 100.128.0.0/24
A 240.0.0.0/13
Q 241.170.96.14 30 363
A 213.0.0.0/30
A 3.0.0.0/20
A 212.0.0.0/7
Q 193.0.0.4 32 348
Q 74.128.0.7 46 329
Q 100.0.0.1 36 370
Q 94.3.0.7 58 326
A 120.0.0.0/29
A 3.0.0.0/22
Q 72.0.0.14 10 356
A 232.0.0.0/25
A 100.200.0.0/24
A 20.30.128.0/19
Q 179.11.0.0 54 346
A 64.0.0.0/11
Q 64.0.0.15 39 336
A 215.172.0.0/24
Q 160.0.0.14 38 358
A 64.0.0.0/12
Q 213.0.0.15 52 380
A 8.0.0.0/17
A 224.0.0.0/30
Q 178.0.0.12 31 369
A 162.0.0.0/23
A 100.200.16.0/20
A 3.128.0.0/16
A 191.0.0.0/16
Q 224.0.0.15 7 368
Q 74.0.0.12 11 375
Q 193.0.0.10 49 327
A 213.0.0.0/24
A 3.128.0.0/25
Q 224.0.0.2 28 381
Q 193.88.0.15 33 386
A 100.0.0.0/15
A 120.0.0.0/12
Q 240.0.0.12 34 334
A 191.0.0.0/9
Q 72.0.0.8 5 355
A 241.160.0.0/29
Q 0.0.0.14 29 341
A 242.128.0.0/10
Q 16.0.0.8 47 349
Q 160.0.0.14 32 338
A 120.0.0.0/19
A 72.0.0.0/23
A 232.0.0.0/18
Q 100.0.0.14 44 369
A 120.0.0.0/23
A 8.0.0.0/10
A 120.0.0.0/21
Q 96.0.0.4 64 392
A 179.0.0.0/18
A 151.0.0.0/9
Q 100.192.0.0 47 340
Q 16.0.0.4 7 381
A 3.192.0.0/14
A 185.212.64.0/22
Q 193.24.0.7 16 395
A 162.0.0.0/31
Q 193.24.0.8 59 381
A 224.0.0.0/19
A 120.0.0.0/27
A 155.0.0.0/8
Q 191.0.0.12 66 394
Q 100.0.0.3 17 403
A 224.0.0.0/23
Q 8.0.0.13 29 364
A 162.0.0.0/30
Q 0.0.0.0 66 403
A 151.48.8.0/29
A 74.128.0.0/29
A 100.0.0.0/20
A 179.11.0.0/28
Q 179.11.0.1 10 381
A 193.0.0.0/26
A 160.0.0.0/19
Q 0.0.0.0 7 394
Q 232.0.0.0 5 359
Q 100.0.0.8 1 360
A 191.0.0.0/21
A 176.0.0.0/6
A 100.128.0.0/28
Q 96.0.0.11 44 391
Q 74.128.0.15 28 362
A 160.0.0.0/23
A 100.200.0.0/31
A 72.0.0.0/25
A 212.0.0.0/13
A 162.0.0.0/19
A 160.0.0.0/30
A 120.0.0.0/20
A 160.0.0.0/26
Q 240.0.0.6 3 373
Q 100.192.0.14 56 409
A 191.11.64.0/26
A 100.200.20.0/26
A 100.0.0.0/22
A 160.0.0.0/7
A 193.16.0.0/31
A 163.214.0.0/23
A 179.0.0.0/23
A 232.0.0.0/31
Q 224.0.0.11 30 400
A 151.48.8.0/24
A 213.0.0.0/16
Q 192.0.0.8 67 417
A 185.208.0.0/13
Q 224.0.0.3 46 375
A 112.0.0.0/31
Q 241.160.0.11 19 422
Q 118.101.128.7 24 397
A 193.24.0.0/24
A 193.24.0.0/31
A 72.0.0.0/29
Q 100.128.0.1 8 362
Q 191.0.0.3 67 401
Q 192.0.0.3 47 376
A 213.0.0.0/23
A 74.128.0.0/30
Q 162.0.0.9 71 387
A 3.192.0.0/20
Q 232.0.0.4 53 374
Q 213.0.0.14 59 393
Q 163.214.0.1 52 391
A 16.0.0.0/18
A 193.0.0.0/27
A 213.0.0.0/15
Q 16.0.0.14 33 363
Q 163.214.0.15 26 387
Q 103.119.244.96 42 417
Q 100.192.0.14 18 380
A 179.0.0.0/29
A 100.200.0.0/22
A 96.0.0.0/10
Q 163.214.0.5 3 376
Q 0.0.0.9 37 403
A 72.0.0.0/15
A 16.160.0.0/22
Q 128.0.0.14 27 437
A 191.0.0.0/31
A 232.0.0.0/27
Q 0.0.0.14 24 415
A 208.0.0.0/4
A 191.0.0.0/14
Q 16.0.0.1 53 378
Q 3.192.0.7 73 392
A 120.0.0.0/9
A 72.0.0.0/26
A 16.0.0.0/31
Q 74.128.0.0 3 416
A 100.200.0.0/17
Q 100.192.0.2 66 398
A 120.0.0.0/24
A 64.0.0.0/31
A 213.128.0.0/17
A 16.0.0.0/22
Q 72.0.0.1 19 440
Q 215.172.0.10 65 437
A 145.16.0.0/13
A 16.0.0.0/21
Q 64.0.0.11 66 413
A 162.0.0.0/14
Q 160.0.0.8 65 432
Q 96.0.0.15 19 432
Q 192.0.0.4 32 395
A 155.0.0.0/21
A 64.0.0.0/30
A 3.128.0.0/11
A 215.128.0.0/9
Q 232.0.0.7 53 382
A 160.0.0.0/8
A 241.0.0.0/8
A 0.0.0.0/30
Q 240.0.0.14 59 434
Q 240.0.0.0 6 444
A 144.0.0.0/4
Q 3.192.0.0 14 417
Q 193.24.0.6 72 384
A 96.0.0.0/26
A 62.170.234.0/30

Hint

2.route

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

数据范围：

设一条表项的掩码长度为L，数据保证将目的地址转为二进制串后，末尾的32-L位均为0

#2881. [Cqoi2016]路由表

[Cqoi2016]路由表

Description

Format

Input

Output

Samples

Hint

#2881. [Cqoi2016]路由表

[Cqoi2016]路由表

Description

Format

Input

Output

Samples

Hint

还没有账户？

登录