F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 3946. -- 无聊的游戏

3946: 无聊的游戏

Time Limit: 40 Sec  Memory Limit: 512 MB
Submit: 353  Solved: 81
[Submit][Status][Discuss]

Description

小K因为学习OI认识了两位神犇,他们分别叫做小H和小Y。两位神犇平时是这么对待小K的:
“这不是道傻逼题么”
“这都不会做你智商堪忧啊”
“。。。。。。”
小K因此对生活失去了信心。最近两位神犇没什么题刷,于是他们开始用自己做题剩下的史诗级智商来享受生活的快乐——研究游戏开发了。
由于两位神犇太神,不久他们就创造了新的游戏。游戏一开始会给由你N个非空串构成的序列,然后你要进行M次操作。操作分为两种:
第一种操作Insert(L,R,S):表示在[L,R]之间的所有串前都加上一个新的非空串S。
第二种操作Query(L,R):询问[L,R]之间所有串的最长公共前缀。如果L=R,则输出对应串的长度。
两位神犇分分钟就把这个游戏玩通了。于是他们准备虐一虐小K,让他也来玩玩。不出所料,小K被虐得头昏眼花,于是他找到你,看你能不
能帮他一把。小K还需要为NOIP一等奖而奋斗呢。

Input

第1行包含两个正整数N,M。接下来的N行每行都包含一个非空的串S,表示第i个初始的串。再接下来的M行每行的
开头都有一个字母type,type=`I'表示这行对应一个Insert操作,而type=`Q'时对应一个Query操作。接下来会从
左到右依次给出这个操作的参数。

Output

对于每一个Query操作,输出一行。一行包含一个正整数,表示这组询问的答案。

Sample Input

2 3
noi
noip
Q 1 2
I 2 2 ctsc
Q 1 2

Sample Output

3
0

HINT


令st表示初始时所有串的长度之和,$sum$表示所有$Insert$操作中所给串的长度之和。

对于25%的数据,满足N,M<=1000, st,sum<=3000。

对于50%的数据,满足N,M<=20000, st,sum<=40000。

对于100%的数据,满足N,M<=50000,st+sum<=600000

保证所有的串都只包含小写英文字母。

保证有一些数据是随机的。


Source

2014年国家集训队十五人互测

[Submit][Status][Discuss]

HOME Back