#P7454. [2017年杭电多校]String and String

    ID: 7467 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-后缀自动机endpos 等价类树上倍增子树转区间二维树状数组离线预收集坐标局部离散化

[2017年杭电多校]String and String

String and String

Problem Description

You are given two strings S and T ,we define the "Sval" :

  1. consider the substring T.substring(ai⊗ans,bi⊗ans)T.substring(a_i\otimes ans,b_i\otimes ans) in the substring S.substring(ci⊗ans,di⊗ans)S.substring(c_i\otimes ans,d_i\otimes ans) perfect matching.
  2. assume all the positions of matching is [x0,y0],[x1,y1]...[xk,yk][x_0,y_0],[x_1,y_1]...[x_k,y_k] while T.substring(ai⊗ans,bi⊗ans)T.substring(a_i\otimes ans,b_i\otimes ans)=S.substring(x0,y0)S.substring(x_0,y_0)=S.substring(x1,y1)S.substring(x_1,y_1)=...=S.substring(xk,yk)S.substring(x_k,y_k) $\quad (c_i\otimes ans\leq x_i,y_i\leq d_i\otimes ans)$
  3. define then Sval=∑i=0kf[yi] Sval=\sum_{i=0}^{k}f[y_i] And Zhu thinks it's too easy and he can modify the f[ai⊗ans]f[a_i\otimes ans] to bi⊗ansb_i\otimes ans. note:
  4. the "ansans" shows before is the answer of the last query,at first ans=0.
  5. the symbol "⊗\otimes" is xor in binary system
  6. the index is 0-based

Input

The first line is an integer T(1≤T≤101 \leq T \leq 10) describe the number of test cases. Each test case begins with two strings S and T,(∣S∣,∣T∣≤100000,∑∣S∣+∣T∣≤400000|S|,|T|\leq 100000,\sum{|S|+|T|}\leq 400000,each character is lowercase letters from the alphabet). Then a line contains ∣S∣|S| numbers describe each element of ff.(0≤fi≤100000 \leq f_i \leq 10000) The next line contains number of operators Q (Q≤100000,∑Q≤200000Q\leq 100000,\sum{Q}\leq 200000). The operators have two types: 1.modify the f[ai⊗ans]f[a_i\otimes ans] to bi⊗ansb_i\otimes ans (0≤bi⊗ans≤100000\leq b_i\otimes ans\leq 10000) 2.query the Sval of T.substring(ai⊗ans,bi⊗ans)T.substring(a_i\otimes ans,b_i\otimes ans) in S.substring(ci⊗ans,di⊗ans)S.substring(c_i\otimes ans,d_i\otimes ans) The remaining Q lines contain operators in the form ti ai bit_i\ a_i\ b_i if ti=1t_i=1;ti ai bi ci dit_i\ a_i\ b_i\ c_i\ d_i if ti=2t_i=2 denoting the type of the operators and the parameters respectively.

Output

For each query output one integer which means the answer.

Sample Input

1

aaaa

aaaa

0 1 2 3

3

2 0 0 0 3

1 6 3

2 6 6 6 5

Sample Output

6

11

Source

2017 Multi-University Training Contest - Team 2

https://acm.hdu.edu.cn/showproblem.php?pid=6054