题目
P3372 【模板】线段树 1
####题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 k。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数n, m，分别表示该数列数字的个数和操作的总个数。
第二行包含n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：
1 x y k：将区间 [x, y][x,y] 内每个数加上 kk。2 x y：输出区间 [x, y][x,y] 内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
输入输出样例
1
2
3
4
5
6
7
| 5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
|
说明/提示
对于 30% 的数据：n≤8，m≤10。
对于 70% 的数据：n≤10^3^，m≤10^4^。
对于 100% 的数据：1≤n,m≤10^5^。
保证任意时刻数列中任意元素的和在 [-263, 263)内。
【样例解释】
代码
不多说了，线段树板子题。
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000090;
long long nums[MAXN];
long long totN;
long long totDO;
bool tempquest;
struct Node
{
long long tag;
long long value;
long long l, r;
Node* lch, * rch;
inline void maketag(const long long w)
{
value += (r - l + 1) * w;
tag += w;
}
inline void push_up()
{
value = lch->value + rch->value;
}
inline void push_down()
{
if (!tag)
{
return;
}
else
{
if (lch==NULL)
{
Node(l, (l + r) >> 1);
}
if (rch == NULL)
{
Node(((l + r) >> 1) + 1, r);
}
lch->maketag(tag);
rch->maketag(tag);
tag = 0;
}
}
Node(const long long L, const long long R)
{
l = L;
r = R;
if (l == r)
{
value = nums[l];
lch = NULL;
rch = NULL;
tag = 0;
}
else
{
tag = 0;
long long mid = (l + r) >> 1;
lch = new Node(L, mid);
rch = new Node(mid + 1, R);
push_up();
}
}
inline bool in_range(const long long L, const long long R)
{
return (L <= l) && (R >= r);
}
inline bool out_of_range(const long long L, const long long R)
{
return (l > R) || (r < L);
}
inline void update(const long long L, const long long R, const long long w)
{
if (in_range(L, R))
{
maketag(w);
}
else if (!out_of_range(L, R))
{
push_down();
lch->update(L, R, w);
rch->update(L, R, w);
push_up();
}
}
inline long long quest_range_sum(const long long L, const long long R)
{
if (in_range(L, R))
{
return value;
}
else
{
if (out_of_range(L, R))
{
return 0;
}
}
push_down();
return lch->quest_range_sum(L, R) + rch->quest_range_sum(L, R);
}
};
inline long long read()
{
long long x = 0;
short f = 1;
char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void write(const long long& x)
{
char f[100];
long long tmp = x;
if (tmp < 0)
{
tmp = -tmp;
putchar('-');
}
long long s = 0;
while (tmp > 0)
{
f[s++] = tmp % 10 + '0';
tmp /= 10;
}
while (s > 0)
{
putchar(f[--s]);
}
}
int main()
{
totN = read();
totDO = read();
int temp;
for (int i = 1; i <= totN; i++)
{
nums[i] = read();
}
Node* root = new Node(1, totN);
for (int i = 1; i <= totDO; i++)
{
tempquest = read() - 1;
if (!tempquest)
{
long long tempL = read();
long long tempR = read();
auto tempW = read();
root->update(tempL, tempR, tempW);
}
else
{
auto tempL = read();
auto tempR = read();
write(root->quest_range_sum(tempL, tempR));
putchar('\n');
}
}
return 0;
}
|
