Codeforces 710F 字典树+后缀数组构成支持修改的AC自动机

http://codeforces.com/contest/710/problem/F

String Set Queries

time limit per test

3 seconds

memory limit per test

768 megabytes

You should process m queries over a set D of strings. Each query is one of three kinds:

  1. Add a string s to the set D. It is guaranteed that the string s was not added before.
  2. Delete a string s from the set D. It is guaranteed that the string s is in the set D.
  3. For the given string s find the number of occurrences of the strings from the set D. If some string p from D has several occurrences in s you should count all of them.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query of the third type. Use functions fflush in C++ and BufferedWriter.flush in Java languages after each writing in your program.

Input

The first line contains integer m (1 ≤ m ≤ 3·105) — the number of queries.

Each of the next m lines contains integer t (1 ≤ t ≤ 3) and nonempty string s— the kind of the query and the string to process. All strings consist of only lowercase English letters.

The sum of lengths of all strings in the input will not exceed 3·105.

Output

For each query of the third kind print the only integer c— the desired number of occurrences in the string s.

Examples
Input

Output

Input

Output

题意:

有一个字符串的集合D,和Q次操作。每次操作可能向D集合插入一个字符串,或者在D集合中删除一个字符串,或者询问在集合D中的所有字符串,在询问串中出现了多少次。强制在线。

题解:

由于存在删除和插入,所以不能直接用AC自动机解决这个问题。考虑插入和删除用字典树来维护,对于每一次询问,构建询问串的后缀数组,按照后缀字典序,将每一个后缀在字典树中进行查询,统计答案即可。当询问完第i个后缀后,直接在字典树上暴力退回到后一个串的height位置即可。下一个串直接从这个位置开始查询字典树。

 

HDU 5845 Best Division xor字典树优化DP转移

http://acm.split.hdu.edu.cn/showproblem.php?pid=5845

Best Division

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem Description

You are given an array A, consisting of N integers.

You are also given 2 integers K and L.

You must divide the whole array A into exactly K nonempty intervals, such that the length of each interval is not greater than L.

The cost of an interval [S, E] is the bitwise XOR sum of all elements of A whose indices are in [S, E].

The score of a division is simply the maximum cost of K intervals in the division. You are interested in the best division, which minimizes the score of the division. Since this is too simple for you, the problem is reversed.

You know the minimum score: the answer for the original problem is not greater than X. Now you want to know, the maximum value of K.

Input

There are several test cases.

The first line of the input contains an integer T (1<=T<=20), the number of test cases. Then T test cases follow.

Each test case starts with 3 integers N, X, L (1<= L<=N<=100000, 0<=X<268435456), which are described above.

The next line contains 3 integers A[1], P, Q. All other integers of the array A are generated from these 3 integers in the following rule:

For every integer 1<k<=N, A[k] = (A[k-1]*P+Q) mod 268435456.
(0 <= A[1], P, Q < 268435456)

Output

For each test case, you should print a single line containing the answer.

If the answer does not exist, just print 0.

Sample Input

2
3 1 2
1 1 1
3 0 3
1 1 1

Sample Output

2
1

Author

金策工业综合大学(DPRK)

Source

 2016 Multi-University Training Contest 9 

题意

给一一对数P和Q和一个数A[1],生成一个数组A[k] = (A[k-1]*P+Q) mod 268435456,总长度为N。将该数组进行分段,每段长度不超过L,且每段的异或和不超过X,问最多能分成多少段。 (1<= L<=N<=100000, 0<=X<268435456)。

题解

很容易想到一个O(N2)的DP转移方程,但是明显复杂度是不够的,需要进行优化。在求第i位置的DP值的时候,将这个位置之前的前L个异或前缀和插入字典树,并用字典树维护其DP的最大值。在查询的时候,假设当前位置的异或和为x,每段的异或和不超过X,那么对于某一个位,如果X的这一位为1,那么x可以尝试走到使这一位异或等于0的节点,以后不管再怎样走,异或值都不会超过X,所以,这种情况直接取这个节点dp值就好了,那么如果走到异或等于1的地方,就成了一个类似的问题,递归查找即可,直接获取的dp值和查询值取max即可。对于X的这一位为0的,就只能递归查找使这一位异或等于0的节点。对于已经删除的节点,我们直接将其dp值标记为-1就好了。