配点: 100 点
問題文
在JOIG国使用JOIG语,在JOIG语中,文字 A, B, C, D, E, F, G, H, I, J, K, L, M, N, O 可以得到第 15 种类的字符被使用.
下个月在JOIG国举办的打字比赛中,将竞争输入由JOIG语使用的 15 种类的字符组成的长度 N 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字. S 参赛者
- 使用1 根手指进行打字.
- 使用15 种类的字符键 1 个一组地 1 列排布,使用左右细长的键盘。此外,哪个位置放哪个字符的键,由参与者自由决定。
- 参与者将通过打出字符串 S 可以得到第 1, 2, \dots, N 第几个字符的键按这个顺序来输入字符串 S 。
预计有 Q 人参加本次比赛。参与者的打字能力各不相同。i 番目 (1 \leqq i \leqq Q)的参与者在打字时需要以下时间。
- 按位于手指正下方的键 1 次需要 A_i 毫秒。
- 将手指 1 移动到左边第几个键上需要 L_i 毫秒。
- 将手指 1 移动到右边第几个键上需要 R_i 毫秒。
文字列 S ,并且给出每位参与者的信息,因此对于每位参与者,可以对字符串 S 从开始输入第一个字符到输入最后一个字符所需的最短毫秒数的程序。
制約
- 1 \leqq N \leqq 1\,000\,000.
- S 是长度 N 的字符串.
- S 的每个字符是
A,B,C,D,E,F,G,H,I,J,K,L,M,N,O的其中之一. - 1 \leqq Q \leqq 150\,000.
- 1 \leqq A_i \leqq 10^{11} (1 \leqq i \leqq Q).
- 1 \leqq L_i \leqq 10^{11} (1 \leqq i \leqq Q).
- 1 \leqq R_i \leqq 10^{11} (1 \leqq i \leqq Q).
- N, Q, A_i, L_i, R_i 是整数.
小課題
- (2 点) S 的每个字符是
A是,Q = 1. - (3 点) S 的每个字符是
A,B之一Q = 1. - (4 点) S 的每个字符是
A,B,C之一Q = 1. - (9 点) S 的每个字符是
A,B,C,D,E,F,G,H之一Q = 1,N \leqq 100. - (14 点) S 的每个字符是
A,B,C,D,E,F,G,H之一Q = 1. - (26 点) S 的每个字符是
A,B,C,D,E,F,G,H的其中之一. - (23 点) Q = 1.
- (7 点) L_i = R_i (1 \leqq i \leqq Q).
- (12 点)没有额外的限制。
入力
输入按以下格式给出。
N S Q A_1 L_1 R_1 A_2 L_2 R_2 \vdots A_Q L_Q R_Q
出力
Q 行输出。i 行目 (1 \leqq i \leqq Q)有参与者 i 从开始输入第一个字符到输入最后一个字符所需的最短毫秒数 S 输出字符串
入力例 1
6 ABAABB 1 100 150 210
出力例 1
1110
例如,考虑键盘的排列顺序从左到右为 ONMLKJIHGFEDCBA 。在这种情况下,通过执行下表中的动作, 1\,110 毫秒可以输入字符串 ABAABB 。
| 手順 | 動作 | 手指正下方的键 | 时间(毫秒) |
|---|---|---|---|
| 1 | 按 A 键 | A | 100 |
| 2 | 将手指 1 向左移动一个键 | A → B | 150 |
| 3 | 按 B 键 | B | 100 |
| 4 | 将手指 1 向右移动一键 | B → A | 210 |
| 5 | 按 A 键 | A | 100 |
| 6 | 按 A 键 | A | 100 |
| 7 | 将手指 1 向左移动一个键 | A → B | 150 |
| 8 | 按 B 键 | B | 100 |
| 9 | 按 B 键 | B | 100 |
除了上面列出的键盘布局之外,您还可以
有多种方法可以在相同的时间内输入 ABAABB ,但无法在更短的时间内输入。因此 1\,110 。
你只需要砍掉
此输入示例是一个小作业。 2, 3, 4, 5, 6, 7, 9 满足约束。
入力例 2
6 CBACAB 1 150 240 220
出力例 2
2260
例如,考虑键盘的排列顺序从左到右为 CABDEFGHIJKLMNO 。在这种情况下,通过执行下表中的动作,2\,260 毫秒可以输入字符串 CBACAB 。
| 手順 | 動作 | 手指正下方的键 | 时间(毫秒) |
|---|---|---|---|
| 1 | 按 C 键 | C | 150 |
| 2 | 将手指 1 向右移动一键 | C → A | 220 |
| 3 | 将手指 1 向右移动一键 | A → B | 220 |
| 4 | 按 B 键 | B | 150 |
| 5 | 将手指 1 向左移动一个键 | B → A | 240 |
| 6 | 按 A 键 | A | 150 |
| 7 | 将手指 1 向左移动一个键 | A → C | 240 |
| 8 | 按 C 键 | C | 150 |
| 9 | 将手指 1 向右移动一键 | C → A | 220 |
| 10 | 按 A 键 | A | 150 |
| 11 | 将手指 1 向右移动一键 | A → B | 220 |
| 12 | 按 B 键 | B | 150 |
除了上面列出的键盘布局之外,字符串 CBACAB ,但无法在更短的时间内输入。因此 2\,260 。
你只需要砍掉
此输入示例是一个小作业。 3, 4, 5, 6, 7, 9 满足约束。
入力例 3
20 AAAAAAAAAAAAAAAAAAAA 1 230000000 80000000 80000000
出力例 3
4600000000
A 该值应乘以 20 次,因此无论键盘布局如何,完成打字所需的时间都是最短的。 230\,000\,000 \times 20 = 4\,600\,000\,000 需要几毫秒。因此 4\,600\,000\,000 。
你只需要砍掉
此输入示例满足所有子任务约束。
入力例 4
7 EACHBAG 5 130 104 162 107 219 45 144 168 157 213 79 257 100000000000 100000000000 100000000000
出力例 4
2078 1766 2465 2894 1600000000000
此输入示例是一个小作业。 6, 9 满足约束。
入力例 5
19 JOIGCODINGCHALLENGE 5 1 1 1 100 200 200 225 111 111 123456789 987654321 987654321 31415926535 27182818284 27182818284
出力例 5
48 7700 7494 30987654300 1385204334401
此输入示例是一个小作业。 8, 9 满足约束。