8628: BZOJ4628:[BeiJing2016]IP地址

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

路由表中每一项对应了一个形如 1011101?????????????????????????的规则,会匹配指定的前缀为给定形式的 ip 。 当有多个规则匹配时,前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。每一个时刻,会有一 条规则被加入,或者之前被加入的某条规则会过期。给一系列 ip,问每一个 ip 在一个给定的时间区间内匹配到 的生效规则变了几次? 例如,有一系列事件: Add 110 Add 11 Del 110 Del 11 Add 110 那么,IP 地址 11011101001001010101011101000010在这五个时刻之后匹配到 的生效规则分别是: 110(第一条), 110(第一条), 11(第二条), 空, 110(第三条)。 其中,在第二个事件后到第五个事件后的这段过程中,一共变了3次。


输入格式

第一行两个整数 N 和 Q,表示时刻的个数与查询的个数。 接下来 N 行,每行描述一个事件。事件的格式是 Add s 表示新建一个规则,匹配前缀为 s 的所有 ip. Del s 表示把当前前缀 s 对应的规则删掉(过期)。保证之前有这样的一条规则还没被删。 接下来 Q 行,每行一个 ip 与两个整数 a,b,表示查询 ip 在第 a 个事件(从 1 开始数) 后到第 b 个事件后的这段时间里,这个 ip 匹配到的生效规则变化的次数。 ip 用01字符串来表示。 1 ≤ N, Q ≤ 10^5,串长不超过32


输出格式

对每个查询,输出所求的变化次数.


样例输入

5 1
Add 110
Add 11
Del 110
Del 11
Add 110
11011101001001010101011101000010 2 5

样例输出

3

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: