Сумма квадратов на дереве отрезков
Сумма квадратов на дереве отрезков
Деревья отрезков чрезвычайно полезны. Например, при "Ленивом проталкивании" (которое позволяет вычислять сумму на отрезке за O(lg(n)) и обновление на отрезке за O(lg(n)). В этой задаче Вам следует вычислить сумму квадратов на отрезке с возможностью двух типом модификаций:
- увеличение на отрезке
- присваивание на отрезке.
Входные данные
Первая строка содержит количество тестов. Первая строка каждого теста содержит два целых числа n (n ≤ 105
) и q (q ≤ 105
). Следующая строка содержит n целых чисел, каждое из которых не больше 1000 по модулю. Каждая из следующих q строк начинается с числа, указывающего на тип операции:
- 2 st nd – вывести сумму квадратов чисел с индексами [st, nd] {то есть от st до nd включительно} (1 ≤ st ≤ nd ≤ n).
- 1 st nd x – добавить "x" ко всем числам с индексами [st, nd] (1 ≤ st ≤ nd ≤ n и -1000 ≤ x ≤ 1000).
- 0 st nd x – установить все числа с индексами [st, nd] равными "x" (1 ≤ st ≤ nd ≤ n и -1000 ≤ x ≤ 1000).
Выходные данные
Для каждого теста вывести “Case <caseno>:” в первой строке, а далее в каждой строке выводить сумму квадратов - результат операции типа 2. Можно избежать переполнения, если использовать 64-битный знаковый целочисленный тип.
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
Case 1: 30 7 13 Case 2: 1