A Simple Problem with Integers
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 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
Hint
The sums may exceed the range of 32-bit integers.
Source
POJ Monthly--2007.11.25, Yang Yi
题目类型：线段树
算法分析：这是一道线段树成段更新和区间求和的问题，要使用lazy标记，注意结果可能超过int范围，所以应该使用long long来存储结果
|
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 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 10000007; const int maxn = 100000 + 66; long long lazy[maxn<<2]; long long sum[maxn<<2]; void PushUp (int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void PushDown (int rt, int l, int m, int r) { if (lazy[rt]) { lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt]; sum[rt<<1] += lazy[rt] * (m - l + 1); sum[rt<<1|1] += lazy[rt] * (r - m); lazy[rt] = 0; } } void Build (int rt, int l, int r) { lazy[rt] = 0; if (l == r) { scanf ("%lld", &sum[rt]); return ; } int m = (l + r) >> 1; PushDown (rt, l, m, r); Build (lson); Build (rson); PushUp (rt); } void UpDate (int rt, int l, int r, int L, int R, int add) { if (L <= l && r <= R) { lazy[rt] += add; sum[rt] += add * (r - l + 1); return ; } int m = (l + r) >> 1; PushDown (rt, l, m, r); if (L <= m) UpDate (lson, L, R, add); if (R > m) UpDate (rson, L, R, add); PushUp (rt); } long long Query (int rt, int l, int r, int L, int R) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; PushDown (rt, l, m, r); long long ans = 0; if (L <= m) ans += Query (lson, L, R); if (R > m) ans += Query (rson, L, R); return ans; } int main() { // freopen ("aaa.txt", "r", stdin); int n, q; while (scanf ("%d%d", &n, &q) != EOF) { Build (1, 1, n); int i, val_a, val_b, val; char cmd[6]; for (i = 0; i < q; i++) { scanf ("%s%d%d", cmd, &val_a, &val_b); if (cmd[0] == 'Q') printf ("%lld\n", Query (1, 1, n, val_a, val_b)); else { scanf ("%d", &val); UpDate (1, 1, n, val_a, val_b, val); } } } return 0; } |
- « 上一篇：poj3320
- poj3641：下一篇 »