SPOJSolutions/HORRIBLE.cpp at master · narutoamu/SPOJSolutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>

using namespace std;

struct Node
{
	long long Sum, Lazy;
	Node() {Sum = Lazy = 0;}
};

Node SegTree[4000001];

void Refresh()
{
	for (int i = 0; i <= 4000000; i++)
		SegTree[i] = Node();
}

void UpdateRange(int i, int STx1, int STx2, int x1, int x2, long long V)
{
	if (SegTree[i].Lazy != 0)
	{
		SegTree[i].Sum += (STx2 - STx1 + 1)*SegTree[i].Lazy;

		if (STx1 != STx2)
		{
			SegTree[2*i].Lazy += SegTree[i].Lazy;
			SegTree[2*i + 1].Lazy += SegTree[i].Lazy;
		}
		SegTree[i].Lazy = 0;
	}

	if (x1 > x2 || x2 < STx1 || x1 > STx2 || STx1 > STx2)
		return;

	if (STx1 >= x1 && STx2 <= x2)
	{
		SegTree[i].Sum += (STx2 - STx1 + 1)*V;

		if (STx1 != STx2)
		{
			SegTree[2*i].Lazy += V;
			SegTree[2*i + 1].Lazy += V;
		}
	}
	else
	{
		int STxm = (STx1 + STx2)/2;
		UpdateRange(2*i, STx1, STxm, x1, x2, V);
		UpdateRange(2*i + 1, STxm + 1, STx2, x1, x2, V);
		SegTree[i].Sum = SegTree[2*i].Sum + SegTree[2*i + 1].Sum;;
	}
}

Node Query(int i, int STx1, int STx2, int x1, int x2)
{
	if (SegTree[i].Lazy != 0)
	{
		SegTree[i].Sum += (STx2 - STx1 + 1)*SegTree[i].Lazy;

		if (STx1 != STx2)
		{
			SegTree[2*i].Lazy += SegTree[i].Lazy;
			SegTree[2*i + 1].Lazy += SegTree[i].Lazy;
		}
		SegTree[i].Lazy = 0;
	}

	if (x1 > x2 || x2 < STx1 || x1 > STx2 || STx1 > STx2)
		return Node();

	if (STx1 >= x1 && STx2 <= x2)
		return SegTree[i];

	int STxm = (STx1 + STx2)/2;
	Node Ans, Left = Query(2*i, STx1, STxm, x1, x2), Right = Query(2*i + 1, STxm + 1, STx2, x1, x2);
	Ans.Sum = Left.Sum + Right.Sum;
	return Ans;
}

int main()
{
	int T, N, Q, IsQuery, L, R;
	long long V;
	cin>>T;
	while (T--)
	{
		Refresh();
		cin>>N>>Q;
		while (Q--)
		{
			cin>>IsQuery>>L>>R;
			if (IsQuery)
				cout<<Query(1, 1, N, L, R).Sum<<endl;
			else
			{
				cin>>V;
				UpdateRange(1, 1, N, L, R, V);
			}
		}
	}
	return 0;
}