Сума квадратів на дереві відрізків#3984

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

1 секунда

122,174 мегабайта

Дуже легка

Дерева відрізків — надзвичайно корисна структура даних. Наприклад, використовуючи ліниве просування (lazy propagation), можна ефективно виконувати операції: обчислення суми на відрізку за $O (lo g n)$ O(\log n) та оновлення на відрізку за $O (lo g n)$ O(\log n).

У цій задачі вам потрібно обчислювати суму квадратів на заданому відрізку, при цьому підтримуючи два типи модифікацій:

додавання заданого значення до всіх елементів на відрізку,
присвоєння заданого значення всім елементам на відрізку.

Вхідні дані

Перша стрічка містить кількість тестів.

Перша стрічка кожного тесту містить два цілі числа $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) та $q (1 \leq q \leq 1 0^{5})$ q~(1 \le q \le 10^5).

Наступна стрічка містить $n$ цілих чисел, кожне з яких по модулю не перевищує $1000$ . Далі йдуть $q$ стрічок, кожна з яких описує одну операцію:

$2 s t n d$ — виведіть суму квадратів елементів з індексами від $s t$ до $n d (1 \leq s t \leq n d \leq n)$ nd~(1 \le st \le nd \le n) включно,
$1 s t n d x$ 1~st~nd~x — додати значення $x$ до всіх елементів відрізка $[s t, n d] (1 \leq s t \leq n d \leq n, - 1000 \leq x \leq 1000)$ [st, nd]~(1 \le st \le nd \le n, -1000 \le x \le 1000),
$0 s t n d x$ 0~st~nd~x — присвоїти значення $x$ всім елементам відрізка $[s t, n d] (1 \leq s t \leq n d \leq n, - 1000 \leq x \leq 1000)$ [st, nd]~(1 \le st \le nd \le n, −1000 \le x \le 1000).

Вихідні дані

Для кожного тесту в першій стрічці виведіть "Case <caseno>:". Потім для кожної операції типу $2$ виведіть значення суми квадратів на відповідному відрізку.

Щоб уникнути переповнення, використовуйте $64$ -бітний знаковий цілочисельний тип даних.

Приклади

Приклад 1