E - Hash Swapping
Editorial
/
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
英小文字からなる長さNの文字列が M 個与えられ、 S_1, S_2, ..., S_M とします。以下のクエリを Q 個処理して下さい。
- swapクエリ(type = 1, x, y, l, r): S_x[l..r] とS_y[l..r] をswapする。
- hashクエリ(type = 2, x, y = 0, l, r): h(S_x[l..r]) を求め,出力する。
なお、
- 文字列 S に対し、S[l..r] を、Sのl文字目からr文字目まで(両端含む)の部分文字列を表すこととします。
- 英小文字 a に対し、ord(a) = 1, ord(b) = 2, ..., ord(z) = 26 とします。
- 文字列 S = c_1c_2...c_k に対し、\sum_{i=1..k} {\rm ord}(c_i)(1,000,000)^{i-1} を 10^9 + 7 で割ったあまりを h(S) とします。
制約
- 1 \leq N \leq 200,000
- 1 \leq M \leq 20
- S_i は英小文字のみからなる
- 1 \leq Q \leq 200,000
- type_i = 1, 2
- 1 \leq x_i \leq M
- swapクエリのとき, x_i < y_i \leq M
- hashクエリのとき、y_i = 0
- 1 \leq l_i \leq r_i \leq N
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 : S_M Q type_1 x_1 y_1 l_1 r_1 type_2 x_2 y_2 l_2 r_2 : type_Q x_Q y_Q l_Q r_Q
出力
各hashクエリに対し、h(S_x[l..r]) を出力してください。
入力例 1
5 2 abcde fghij 8 2 1 0 2 3 2 2 0 1 5 1 1 2 2 2 2 1 0 2 3 2 2 0 1 5 1 1 2 1 3 2 1 0 2 3 2 2 0 1 5
出力例 1
3000002 496944447 3000007 491944447 8000002 496979442
それぞれ、
- h("bc") = 3000002
- h("fghij") = 496944447
- h("gc") = 3000007
- h("fbhij") = 491944447
- h("bh") = 8000002
- h("agcij") = 496979442
を出力しています。
入力例 2
7 3 pzocuwt ghqsktw ogvyhak 13 2 1 0 1 2 1 1 2 5 6 1 1 3 3 6 1 2 3 4 5 1 2 3 5 6 1 1 2 1 6 1 1 2 5 6 2 2 0 5 5 2 1 0 2 3 1 2 3 1 4 1 1 2 2 7 2 3 0 1 6 2 3 0 1 4
出力例 2
26000016 21 17000008 556958241 25847241