8002. Horrible Queries

World is getting more evil and it's getting tougher to get into the Evil League of Evil. Since the legendary Bad Horse has retired, now you have to correctly answer the evil questions of Dr. Horrible, who has a PhD in horribleness (but not in Computer Science). You are given an array of n elements, which are initially all 0. After that you will be given c commands. They are:

· 0 p q v – you have to add v to all numbers in the range of p to q inclusive, where p and q are two indexes of the array.

· 1 p q – print a line containing a single integer which is the sum of all the array elements between p and q inclusive.

Input. The first line contains the number of test cases. Each test case starts with n (n ≤ 100 000) and c (c ≤ 100 000). After that you'll be given c commands in the format as mentioned above. It is known that 1 ≤ p, q ≤ n and 1 ≤ v ≤ 10⁷.

Output. Print the answers to the queries.

Sample input

1

8 6

0 2 4 26

0 4 8 80

0 4 5 20

1 8 8

0 5 7 14

1 4 8

Sample output

80

508

РЕШЕНИЕ

структуры данных – дерево отрезков

Анализ алгоритма

Для решения задачи следует реализовать дерево отрезков, поддерживающее групповую модификацию – прибавление и суммирование.

В каждом узле дерева будут поддерживаться значения двух переменных: суммы на отрезке summa и некоторого дополнительного значения add, которое следует прибавить ко всем элементам отрезка. Протолкнуть значение add по дереву на один уровень ниже означает прибавить его к значению summa левого и правого поддерева, умноженного на длину соответствующего отрезка, а также к значению add левого и правого поддерева, тем самым рекурсивно обеспечив проталкивание значения add до листьев дерева.

Операцию проталкивания следует производить не только при выполнении операции прибавления на отрезке, но и при вычислении сумм.

Пример

Пусть некоторая вершина соответствует отрезку [0; 5]. Ее сыновьями являются отрезки [0; 2] и [3; 5]. Рассмотрим операцию проталкивания на примере.

Реализация алгоритма

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAX 100010

using namespace std;

struct node

{

long long summa, add;

} SegTree[4*MAX];

void Push(int Vertex, int LeftPos, int Middle, int RightPos)

{

if (SegTree[Vertex].add)

{

SegTree[2*Vertex].add += SegTree[Vertex].add;

SegTree[2*Vertex].summa += (Middle - LeftPos + 1) * SegTree[Vertex].add;

SegTree[2*Vertex+1].add += SegTree[Vertex].add;

SegTree[2*Vertex+1].summa += (RightPos - Middle) * SegTree[Vertex].add;

SegTree[Vertex].add = 0;

}

}

void AddValue(int Vertex, int LeftPos, int RightPos,

int Left, int Right, int Value)

{

if (Left > Right) return;

if ((LeftPos == Left) && (RightPos == Right))

{

SegTree[Vertex].add += Value;

SegTree[Vertex].summa += 1LL * (Right - Left + 1) * Value;

return;

}

int Middle = (LeftPos + RightPos) / 2;

Push(Vertex,LeftPos,Middle,RightPos);

AddValue(2*Vertex, LeftPos, Middle, Left, min(Middle,Right), Value);

AddValue(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right, Value);

SegTree[Vertex].summa =

SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;

}

long long Summa(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return 0;

if ((LeftPos == Left) && (RightPos == Right)) return SegTree[Vertex].summa;

int Middle = (LeftPos + RightPos) / 2;

Push(Vertex,LeftPos,Middle,RightPos);

return Summa(2*Vertex, LeftPos, Middle, Left, min(Middle,Right)) +

Summa(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

}

int i, n, c, tests, command;

int L, R, p, q, v;

int main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&c);

memset(SegTree,0,sizeof(SegTree));

for(i = 0; i < c; i++)

{

scanf("%d %d %d",&command,&p,&q);

if (command == 0)

{

scanf("%d",&v);

AddValue(1,0,n-1,p-1,q-1,v);

} else

printf("%lld\n",Summa(1,0,n-1,p-1,q-1));

}

}

return 0;

}