Seqment ağacında kvadratların cəmi#3984
Seqment ağacları — son dərəcə faydalı verilənlər strukturu. Məsələn, tənbəl yayılma (lazy propagation) istifadə edərək, O(\log n) zamanında aralıqda cəmi hesablamaq və O(\log n) zamanında aralığı yeniləmək mümkündür.
Bu tapşırıqda sizə verilmiş aralıqda kvadratların cəmini hesablamaq tələb olunur, və bu prosesdə iki tip modifikasiyaları dəstəkləməlisiniz:
verilmiş dəyəri aralıqdakı bütün elementlərə əlavə etmək,
verilmiş dəyəri aralıqdakı bütün elementlərə təyin etmək.
İlk sətir testlərin sayını ehtiva edir.
Hər bir testin ilk sətiri iki tam ədəd n~(1 \le n \le 10^5) və q~(1 \le q \le 10^5) ehtiva edir.
Növbəti sətir modulu -dan çox olmayan tam ədəd ehtiva edir. Daha sonra hər biri bir əməliyyatı təsvir edən sətir gəlir:
— -yə qədər nd~(1 \le st \le nd \le n) daxil olmaqla indeksləri olan elementlərin kvadratlarının cəmini çıxarın,
1~st~nd~x — aralığın bütün elementlərinə [st, nd]~(1 \le st \le nd \le n, -1000 \le x \le 1000) dəyərini əlavə edin,
0~st~nd~x — aralığın bütün elementlərinə [st, nd]~(1 \le st \le nd \le n, −1000 \le x \le 1000) dəyərini təyin edin.
Hər test üçün ilk sətirdə "Case <caseno>:" çıxarın. Sonra tipli hər əməliyyat üçün müvafiq aralıqdakı kvadratların cəm dəyərini çıxarın.
Həddən artıma yol verməmək üçün bitlik işarəli tam ədəd tipindən istifadə edin.
Nümunə 1