Responsive image

问题 1807 --String and String

1807: String and String

时间限制: 6 Sec  内存限制: 128 MB
提交: 1  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

roblem Description
You are given two strings S and T ,we define the "Sval" :
1. consider the substring T.substring(ai⊗ans,bi⊗ans) in the substring S.substring(ci⊗ans,di⊗ans) perfect matching.
2. assume all the positions of matching is [x0,y0],[x1,y1]...[xk,yk] while
T.substring(ai⊗ans,bi⊗ans)=S.substring(x0,y0)=S.substring(x1,y1)=...=S.substring(xk,yk) (ci⊗ans≤xi,yi≤di⊗ans)
3. define then Sval=∑ki=0f[yi]
And Zhu thinks it's too easy and he can modify the f[ai⊗ans] to bi⊗ans.
note:
1. the "ans" shows before is the answer of the last query,at first ans=0.
2. the symbol "⊗" is xor in binary system
3. the index is 0-based

输入描述

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

输出描述

For each query output one integer which means the answer.

样例输入

1
aaaa
aaaa
0 1 2 3
3
2 0 0 0 3
1 6 3
2 6 6 6 5

样例输出

6
11

来源

 

[提交][状态]
ACM算法攻关部