IP地址
题目描述
路由表中每一项对应了一个形如 1011101????????????????????????? 的规则，会匹配指定的前缀为给定形式的 \texttt{ip}ip。
当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。每一个时刻，会有一条规则被加入，或者之前被加入的某条规则会过期。
给一系列 \texttt{ip}ip，问每一个 \texttt{ip}ip 在一个给定的时间区间内匹配到的生效规则变了几次？
例如，有一系列事件：
\texttt{Add}Add 110110
\texttt{Add}Add 1111
\texttt{Del}Del 110110
\texttt{Del}Del 1111
\texttt{Add}Add 110110
那么，\texttt{ip}ip 地址 11011101001001010101011101000010 在这五个时刻之后匹配到的生效规则分别是：
110110 (第一条)，
110110 (第一条)，
1111 (第二条)，
空，
110110 (第三条)。
其中，在第二个事件后到第五个事件后的这段过程中，一共变了 33 次。
输入输出格式
输入格式： 第一行两个正整数 n,qn,q，表示事件数有询问数。
接下来 nn 行，每行描述一个事件，格式为：
\texttt{Add}Add ss 表示新建一个规则，匹配前缀为 ss 的所有 \texttt{ip}ip。
\texttt{Del}Del ss 表示把当前前缀 ss 对应的规则删掉(过期)。保证之前有这样的一条规则还没被删。
接下来 qq 行，每行一个 \texttt{ip}ip 与两个正整数 a,ba,b，表示查询在第 aa 个事件后到第 bb 个事件的这段时间里，这个 \texttt{ip}ip匹配到的生效规则变化的次数。 \texttt{ip}ip 用01字符串来表示。
输出格式：对于每次查询，输出一行一个整数表示答案。
输入输出样例
说明
【数据范围】
1\le n,q \le 10^51≤n,q≤105
#笔试题目#
查看14道真题和解析
腾讯一面1836人在聊