UOJ Logo

NOI.AC

9S 1024MB
Statistics

题目描述

维护一个小写字母的字符串vector $S$,支持操作:

  • I k s 在第 $k$ 个位置后插入串 $s$(若 $k = 0$ 则插入到序列的开头)。
  • Q l r s 查询串 $s$ 在位置 $[l, r]$ 中的多少个串中出现过。 部分数据强制在线。

输入格式

从标准输入读入数据。

输入共 $M + 1$ 行。

第一行两个非负整数 M, T,表示操作次数及是否需要强制在线。

接下来 M 行,每行表示一个操作,格式如题目描述所示。

为了强制在线,当 $T = 1$ 时,若输入的整数为 $a$,则真实的输入数据为a xor lastans。输入的字符串由小写字母构成,若输入的小写字母在字母表中是第 $b$ 个,真实的小写字母在字母表中是第 $(b + lastans) \bmod 26 + 1$ 个。其中$lastans$ 表示上一次询问的答案,初始 $lastans = 0$。

输出格式

输出到标准输出。

对于每个 $Q$ 操作,输出一行表示答案。

样例

输入

5 0
I 0 orzfsf
I 1 fsforz
Q 1 2 fsf
I 0 orz
Q 1 3 orz

输出

2
3

子任务

令 $L_M$ 为修改串的总长度,$L_Q$ 为询问串的总长度。

对于所有数据,$1 \le M \le M_{max}, 1 \le L_M \le 3M, 1 \le L_Q \le 2M$,解密后 $k$, $l$, $r$ 的值均保证合法。

对于测试点 $1$,在所有 I 操作都进行完后才会出现 Q 操作。

测试点编号 $T$ $M_{max}$ 此部分分值 时限
1 0 $40000$ $10$ $4S$
2 0 $40000$ $20$ $4S$
3 1 $40000$ $20$ $4S$
4 1 $40000$ $20$ $4S$
5 1 $100000$ $30$ $9S$

空间限制:$1024\texttt{MB}$

下载

样例数据下载