增强型LCP

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:3 
Case Time Limit:1000MS

Description

Input

Output

对于每个Lcp(a,b)操作输出最长公共前缀

Sample Input

47 abab L 13 A 1 ab L 1 3 C 56 cb L 1 3 D 1 2 L 1 3

Sample Output

2 4 2 0

Source

看这个规模和时限Splay维护Hash值显然不靠谱。。
关键是修改操作很少。。于是我们平衡一下。。
那么就用块状链表吧。对每个块维护一个hash数组。
假设长度为N，分成S快。。那么可以在O(S+Log(N/S))的时间求出Lcp。。。
同时修改是O(N/S)的。。。
由于修改很少。。把S改的很小就可以让效率大幅提高。。。
由于本人代码能力太差。。就不写了T_T。。。
开哥就是用块链A的。。Orz啊！！！！！！