POJ - 3468 - A Simple Problem with Integers - 线段树Lazy大法

1.题目描述：

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072KTotal Submissions: 107104 Accepted: 33434Case Time Limit: 2000MS

Description

You have N integers, A₁, A₂, ... , A_N. 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 A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of A_a, A_a+1, ... , A_b. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of A_a, A_a+1, ... , A_b.

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 2.题意概述：

对数组A有两种操作Q x y是询问x,y区间的和C x y z是对[x, y]区间内所有数都加z

3.解题思路：

很容易想到用线段树维护，这里是区间更新，可以用lazy大法，简要的说，就是对于一个区间，如果它位于要更新的子区间内，那么就延缓对它儿子区间的更新，这样可以进一步降低update的复杂度。

4.AC代码：

#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <functional> #include <cmath> #include <vector> #include <queue> #include <deque> #include <stack> #include <map> #include <set> #include <ctime> #define INF 0x3f3f3f3f #define maxn 100010 #define lson root << 1 #define rson root << 1 | 1 #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; typedef unsigned long long ull; struct tree { int l, r; ll w, lazy; } t[maxn << 2]; void pushup(int root) { t[root].w = t[lson].w + t[rson].w; } void pushdown(int root) { if (t[root].lazy) { t[lson].lazy += t[root].lazy; t[lson].w += (t[lson].r - t[lson].l + 1) * t[root].lazy; t[rson].lazy += t[root].lazy; t[rson].w += (t[rson].r - t[rson].l + 1) * t[root].lazy; t[root].lazy = 0; } } void build(int l, int r, int root) { t[root].l = l; t[root].r = r; t[root].lazy = 0; if (l == r) { scanf("%lld", &t[root].w); return; } int mid = l + r >> 1; build(l, mid, lson); build(mid + 1, r, rson); pushup(root); } void update(ll c, int l, int r, int root) { if (l <= t[root].l && t[root].r <= r) { t[root].lazy += c; t[root].w += c * (t[root].r - t[root].l + 1); return; } pushdown(root); int mid = t[root].l + t[root].r >> 1; if (l <= mid) update(c, l, r, lson); if (r > mid) update(c, l, r, rson); pushup(root); } ll query(int l, int r, int root) { if (l <= t[root].l && t[root].r <= r) return t[root].w; pushdown(root); int mid = t[root].l + t[root].r >> 1; ll ans = 0; if (l <= mid) ans += query(l, r, lson); if (r > mid) ans += query(l, r, rson); return ans; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif int n, q; char op[3]; while (~scanf("%d%d", &n, &q)) { build(1, n, 1); while (q--) { int a, b; ll c; scanf("%s%d%d", op, &a, &b); if (op[0] == 'Q') printf("%lld\n", query(a, b, 1)); else { scanf("%lld", &c); update(c, a, b, 1); } } } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }