e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin kəməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

ADA University - March 7 - Segment Tree

Сумма квадратов на дереве отрезков

Деревья отрезков чрезвычайно полезны. Например, при "Ленивом проталкивании" (которое позволяет вычислять сумму на отрезке за O(lg(n)) и обновление на отрезке за O(lg(n)). В этой задаче Вам следует вычислить сумму квадратов на отрезке с возможностью двух типом модификаций:

  • увеличение на отрезке
  • присваивание на отрезке.

Входные данные

Первая строка содержит количество тестов. Первая строка каждого теста содержит два целых числа n (n105) и q (q105). Следующая строка содержит n целых чисел, каждое из которых не больше 1000 по модулю. Каждая из следующих q строк начинается с числа, указывающего на тип операции:

2 st nd – вывести сумму квадратов чисел с индексами [st, nd] {то есть от st до nd включительно} (1stndn).

1 st nd x – добавить "x" ко всем числам с индексами [st, nd] (1stndn и -1000x1000).

0 st nd x – установить все числа с индексами [st, nd] равными "x" (1stndn и -1000x1000).

Выходные данные

Для каждого теста вывести “Case <caseno>:” в первой строке, а далее в каждой строке выводить сумму квадратов - результат операции типа 2. Можно избежать переполнения, если использовать 64-битный знаковый целочисленный тип.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 MiB
Giriş verilənləri #1
2
4 5
1 2 3 4
2 1 4
0 3 4 1
2 1 4
1 3 4 1
2 1 4
1 1
1
2 1 1
Çıxış verilənləri #1
Case 1:
30
7
13
Case 2:
1