首页 > 代码库 > 【POJ】3468 A Simple Problem with Integers ——线段树 成段更新 懒惰标记
【POJ】3468 A Simple Problem with Integers ——线段树 成段更新 懒惰标记
A Simple Problem with Integers
Time Limit:5000MS Memory Limit:131072K
Case Time Limit:2000MS
Description
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4
Sample Output
455915
Hint
The sums may exceed the range of 32-bit integers.
题解：本题也是线段树系列的模板题之一，要求的是成段更新+懒惰标记。PS：原题的说明有问题，上面说的“C a b c”中的c的范围其实在int32之外，需要使用long long，否则定是WA，真心坑爹，连WA多次，还是在discuss中看到的原因。
稍微讲解下代码中的一些细节: step<<1 与 step<<1|1，意思分别是step*2 和step*+1，具体为什么，可以回去复习一下二进制的微运算
AC代码如下：
1 #include <cstdio> 2 #include <cstring> 3 4 typedef long long ll; 5 const int LEN = 100000 * 4; 6 7 struct line 8 { 9 int left; 10 int right; 11 ll value; 12 ll lazy; //懒惰标记 13 }line[LEN]; 14 15 void buildt(int l, int r, int step) //建树初始化 16 { 17 line[step].left = l; 18 line[step].right = r; 19 line[step].lazy = 0; 20 line[step].value = http://www.mamicode.com/0; 21 if (l == r) 22 return; 23 int mid = (l + r) / 2; 24 buildt(l, mid, step<<1); 25 buildt(mid+1, r, step<<1|1); 26 } 27 28 void update(int l, int r, ll v, int step) 29 { 30 line[step].value += v * (r-l+1); //更新到当前节点，就在当前节点的value中加上增加的值 31 if (line[step].left == line[step].right) //如果更新到最深处的子节点，返回 32 return; 33 if (line[step].lazy != 0){ //如果有懒惰标记，向下传递懒惰标记且更新两个子节点的值 34 line[step<<1].lazy += line[step].lazy; 35 line[step<<1|1].lazy += line[step].lazy; 36 line[step<<1].value += (line[step<<1].right - line[step<<1].left + 1) * line[step].lazy; 37 line[step<<1|1].value += (line[step<<1|1].right - line[step<<1|1].left + 1) * line[step].lazy; 38 line[step].lazy = 0; 39 } 40 if (line[step].left == l && line[step].right == r){ //如果到达目标线段，做上懒惰标记，返回 41 line[step].lazy = v; 42 return; 43 } 44 int mid = (line[step].left + line[step].right) / 2; 45 if (r <= mid) 46 update(l, r, v, step<<1); 47 else if (l > mid) 48 update(l, r, v, step<<1|1); 49 else{ 50 update(l, mid, v, step<<1); 51 update(mid+1, r, v, step<<1|1); 52 } 53 } 54 55 ll findans(int l, int r, int step) 56 { 57 if (l == line[step].left && r == line[step].right) //如果找到目标线段，返回值 58 return line[step].value; 59 if (line[step].lazy != 0){ //懒惰标记的传递更新，同上 60 line[step<<1].lazy += line[step].lazy; 61 line[step<<1|1].lazy += line[step].lazy; 62 line[step<<1].value += (line[step<<1].right - line[step<<1].left + 1) * line[step].lazy; 63 line[step<<1|1].value += (line[step<<1|1].right - line[step<<1|1].left + 1) * line[step].lazy; 64 line[step].lazy = 0; 65 } 66 int mid = (line[step].left + line[step].right) / 2; 67 if (r <= mid) 68 return findans(l, r, step<<1); 69 else if (l > mid) 70 return findans(l, r, step<<1|1); 71 else 72 return findans(l, mid, step<<1) + findans(mid+1, r, step<<1|1); 73 } 74 75 int main() 76 { 77 //freopen("in.txt", "r", stdin); 78 int n, q; 79 scanf("%d %d", &n, &q); 80 buildt(1, n, 1); 81 for(int i = 1; i <= n; i++){ 82 ll t; 83 scanf("%I64d", &t); 84 update(i, i, t, 1); 85 } 86 for(int i = 0; i < q; i++){ 87 char query[2]; 88 scanf("%s", query); 89 if (query[0] == ‘C‘){ 90 int a, b; 91 ll c; 92 scanf("%d %d %I64d", &a, &b, &c); 93 update(a, b, c, 1); 94 } 95 else if (query[0] == ‘Q‘){ 96 int a, b; 97 scanf("%d %d", &a, &b); 98 printf("%I64d\n", findans(a, b, 1)); 99 }100 }101 return 0;102 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。