Fişierul intrare/ieşire:addk.in, addk.outSursăEJOI 2021, ziua 1
AutorMihai BungetAdăugată decadmium_Voicu Mihai Valeriu cadmium_
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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:
#PunctajRestricţii
1361 ≤ N,Q ≤ 10 000 , K = 1
25610 001 ≤ N,Q ≤ 100 000, K = 1
381 ≤ N,Q ≤ 100 000, 2 ≤ K ≤ 10

Exemplu

addk.inaddk.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?