P5460 [BJOI2016] IP地址
题目描述
路由表中每一项对应了一个形如 1011101????????????????????????? 的规则，会匹配指定的前缀为给定形式的 $\texttt{ip}$。
当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。每一个时刻，会有一条规则被加入，或者之前被加入的某条规则会过期。
给一系列 $\texttt{ip}$，问每一个 $\texttt{ip}$ 在一个给定的时间区间内匹配到的生效规则变了几次？
例如，有一系列事件：
$\texttt{Add}$ $110$
$\texttt{Add}$ $11$
$\texttt{Del}$ $110$
$\texttt{Del}$ $11$
$\texttt{Add}$ $110$
那么，$\texttt{ip}$ 地址 11011101001001010101011101000010 在这五个时刻之后匹配到的生效规则分别是：
$110$ (第一条)，
$110$ (第一条)，
$11$ (第二条)，
空，
$110$ (第三条)。
其中，在第二个事件后到第五个事件后的这段过程中，一共变了 $3$ 次。
输入格式
无
输出格式
无
说明/提示
【数据范围】
$1\le n,q \le 10^5$