Seqment ağacı#5952
Sizə adlı elementdən ibarət bir massiv verilir: a_0, a_1, \ldots, a_{255}. Bu massiv əvvəlcə sıfırlarla doldurulub. Massiv üzərində iki növ əməliyyatı dəstəkləməlisiniz: aralıqda toplama və aralıqda cəmin tapılması.
Aralıqda toplama əməliyyatı \textbf{Add}(L, R, value) şəklində olur, yəni massivdəki a_L, a_{L+1}, \ldots, a_R elementlərinə əlavə edilməlidir. Aralıqda cəmin tapılması əməliyyatı \textbf{Get}(L, R) formasındadır və nəticə olaraq \sum_{i=L}^{R} a_i qaytarmalıdır.
Giriş/çıxış vaxtına qənaət etmək üçün ilk əməliyyat həmişə \textbf{Add}(L, R, 1) olacaq; istifadə ediləcək və verilir. Hər növbəti əməliyyat aşağıdakı kimidir: [ Add((L_new, R_new), (L_new, R_new), 1), ] burada L_{new} və R_{new} belə hesablanır: [ L_new = Get((L, R), (L, R)) p, ] [ R_new = 255 - Get((L, R), (L, R)) p, ] harada əməliyyatı bölmədən qalığı göstərir.
Hər belə əməliyyatdan sonra L := L_{new} və R := R_{new} kimi yenilənir.
Yeganə sətirdə dörd tam ədəd verilir: , , , (1 \leq q \leq 5 \cdot 10^6,\ 0 \leq L \leq R \leq 255,\ 1 \leq p \leq 125); — əməliyyatlarının sayı, və başlanğıc dəyərləri, isə modul.
Bütün əməliyyatlarından sonra \textbf{Get}(0, 255) əməliyyatının nəticəsini çap edin.
Nümunə 1