| Fişierul intrare/ieşire: | addk.in, addk.out | Sursă | EJOI 2021, ziua 1 |
| Autor | Mihai Bunget | Adăugată de |  Voicu Mihai Valeriu •cadmium_ |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Addk
Se consideră un şir A cu N elemente numere naturale A1,. . ., AN si un număr natural K. Se cere să se proceseze Q cerinţe de următoarele două tipuri:
- 1 i1 i2,..., iK: se permută circular la stânga elementele şirului Ai1,..., AiK . Astfel noile valor ale elementelor Ai1, Ai2 , ..., AiK-1 , AiK vor fi Ai2 , Ai2 , ..., AiK , Ai1 . Remarcaţi că i1, i2,... , ik sunt distincte şi nu neapărat in ordine crescătoare.
- 2 l r m: se cere calculul sumei elementelor tuturor subsecvenţelor continue de lungime m din secvenţa Al, Al+1,..., Ar-1, Ar. Remarcaţi că elementele care apar în mai multe secvenţe vor fi adunate de mai multe ori.
Date de intrare
Prima linie a fişierul de intrare addk.in conţine două numere întregi, N şi K. A doua linie conţine N numere întregi: elementele vectorului A. A treia linie conţine un întreg Q, numărul de cerinţe, şi apoi Q linii conţinând cerinţele, care pot fi din cele două tipuri descrise mai sus.
Date de ieşire
În fişierul de ieşire addk.out trebuie să conţină răspunsurile la cerinţele de tip 2, câte unul pe linie
Restricţii
- 0 ≤ Ai ≤ 106
- 1 ≤ l ≤ r ≤ N
- 1 ≤ m ≤ r - l + 1
- În plus:
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 36 | 1 ≤ N,Q ≤ 10 000 , K = 1 |
| 2 | 56 | 10 001 ≤ N,Q ≤ 100 000, K = 1 |
| 3 | 8 | 1 ≤ N,Q ≤ 100 000, 2 ≤ K ≤ 10 |
Exemplu
| addk.in | addk.out |
|---|---|
| 8 3 7 2 5 1 9 3 4 6 3 2 2 7 4 1 2 5 8 2 2 7 3 | 52 50 |
Explicaţie
Prima cerinţă este de tip 2 şi trebuie să calculăm suma elementelor tuturor subsecvenţelor de lungime m = 4 din secvenţa 2, 5, 1, 9, 3, 4. Aceste subsecvenţe sunt (2, 5, 1, 9), (5, 1, 9, 3), (1, 9, 3, 4), iar suma elementelor lor este 52.
A doua cerinţă este de tip 1 şi are ca efect permutarea circulară a elementelor din şirul A, situate pe poziţiile 2, 5, 8. Astfel, şirul A devine 7, 9, 5, 1, 6, 3, 4, 2.
A treia cerinţă este de tip 2 şi trebuie să calculăm suma elementelor tuturor subsecvenţelor de lungime m = 3 din secvenţa 9, 5, 1, 6, 3, 4. Aceste subsecvenţe sunt (9, 5, 1), (5, 1, 6), (1, 6, 3), (6, 3, 4), iar suma elementelor lor este 50.
