TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3615
  • 题目
  • P3615【CQOI2016 Day2】路由表
    限制 : 时间限制 : 30000 MS   空间限制 : 565536 KB
    问题描述

    输入格式

    第一行,一个整数n,表示操作次数。
    接下来n行,每行描述一次操作,操作有两种:
    A D/L
    其中D为一个IP地址,L为整数(1<=L<=32)。天假一条表项至路由表,其目的地址为D,掩码长度为L。下一条地址由于没有用到,故省略。

    Q D a b
    其中,D为一个IP地址,a、b为正整数(a<=b).查询从第a到第b次调价表项期间(含a,b),目的地址D的路由表项选择发生了多少次变化。保证查询时表中至少有b个表项目

    输出格式

    若干行,每行一个整数,表示对应查询操作

    样例输入

    11
    A 0.0.0.0/8
    Q 1.2.3.4 1 1
    A 1.0.0.0/9
    A 1.128.0.0/10
    A 1.0.0.0/10
    A 1.0.0.0/8
    Q 1.2.3.4 1 5
    A 1.2.0.0/16
    A 1.2.3.1/32
    Q 1.2.3.4 5 7
    Q 1.2.3.1 5 7

    样例输出

    0
    2
    1
    2

    提示

    2.route

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

    数据范围:

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