Ерниязға көмектесіңіз
Ернияз циклдық ығыстырулар бойынша есептерді жақсы меңгергісі келді және кездейсоқ есептер жиынтығын жинады. Олардың біреуі күтпеген жерден қиын болып шықты. Ерниязға көмектесіңіз.
Берілген массив \(a\) ұзындығы \(n\) және алмастыру(permutation) \(p\) ұзындығы \(m\). Сондай-ақ \(k\) бонус берілген, әрқайсысы үш бүтін санмен сипатталады \((l, r, c)\):
> Бонус \((l, r, c)\) дегеніміз, егер алмастыру(permutation) \(p\) \(a[l..r]\) ішкі массивінде ішкі реттілік ретінде кездессе, Ернияз \(c\) ұпай алады.
Формалды түрде, алмастыру(permutation) \(p = [p_1, p_2, \dots, p_m]\) \(a[l..r]\) ішінде кездеседі, егер осы шарттар орындалса алмастыру(permutation) берілген кесіндіде кесіндінің ішінде кездеседі. \[l \le i_1 < i_2 < \dots < i_m \le r\] және \[a_{i_1} = p_1, a_{i_2} = p_2, \dots, a_{i_m} = p_m.\]
Ернияз барлық **циклдық ығыстыруларды** қарастыруы керек. Әр ығыстыру үшін бонустардың жалпы сомасын есептеу қажет.
Яғни:
Алдымен бастапқы алмастыру(permutation) \(p = [p_1, p_2, \dots, p_m]\) үшін бонус сомасын есептеңіз.
Содан кейін солға циклдық ығыстыру жасаңыз: \(p = [p_2, p_3, \dots, p_m, p_1]\).
Бұл әрекетті барлық \(m\) ығыстыру үшін қайталаңыз.
Енгізу
Бірінші жолда екі бүтін сан \(n\) және \(m\) (\(1 \le m \le n \le 2\cdot10^5\)) беріледі — массивтің ұзындығы және тізбектің ұзындығы.
Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)) беріледі — массив \(a\).
Үшінші жолда \(m\) әртүрлі бүтін сан \(p_1, p_2, \dots, p_m\) (\(1 \le p_i \le m\)) беріледі — тізбек \(p\).
Төртінші жолда бүтін сан \(k\) (\(1 \le k \le 5\cdot10^5\)) беріледі — бонус саны.
Келесі \(k\) жолдың әрқайсысында үш сан \(l_i, r_i, c_i\) (\(1 \le l_i \le r_i \le n, 1 \le c_i \le 10^9\)) беріледі — бонус сипаттамалары.
Шығару
\(m\) бүтін санды шығарыңыз — әрбір циклдық ығыстыру үшін бонус сомасы, ығыстырулар тәртібі бойынша (бастапқыдан бастап).
Бағалау жүйесі
| Ішкі тапсырма | Қосымша шектеулер | Ұпайлар | Қажет ішкі тапсырмалар |
|---|---|---|---|
| \(0\) | Мысалдар | \(0\) | – |
| \(1\) | \(m \le 2\) | 9 | – |
| \(2\) | \(1 \le m \le n \le 100\), \(1 \le k \le 100\) | 11 | \(0\) |
| \(3\) | \(1 \le m \le n \le 5\cdot 10^3\), \(1 \le k \le 5\cdot 10^3\) | 13 | \(0, 2\) |
| \(4\) | \(1 \le m \cdot n \le 5\cdot 10^6, m \le n \le 2\cdot 10^5\) | 20 | \(0, 2\) |
| \(5\) | Барлық бонус бірдей ұзындықта, яғни \(r_i - l_i + 1 = r_j - l_j + 1\) үшін барлық \(1 \le i \lt j \le k\) | 21 | – |
| \(6\) | Қосымша шектеулер жоқ | 26 | \(0-5\) |
Мысалдар
Енгізу 1
8 3
2 1 5 3 2 8 1 3
1 3 2
4
2 7 3
1 5 7
3 6 1
4 8 5Жауап 1
10 8 12Ескертпелер
Үшінші циклдік ығысу үшін (екі рет солға ығысу), тізбек \(p = [2, 1, 3]\). Бұндай тізбектік элементтер келесі аралықтарда кездеседі: \((l_2, r_2, c_2) = (1, 5, 7)\) және \((l_4, r_4, c_4) = (4, 8, 5)\). Сәйкесінше, жалпы бонус \(7 + 5 = 12\) болады.