A Simple Problem with Integers
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. Source , Yang Yi |
[] [Go Back] [] []
我的解答
/*=============================================================================# FileName: 3468.cpp# Desc: poj 3468# Author: zhuting# Email: cnjs.zhuting@gmail.com# HomePage: my.oschina.net/locusxt# Version: 0.0.1# CreatTime: 2013-12-08 11:25:00# LastChange: 2013-12-08 11:25:00# History:=============================================================================*/#include#include #include #include #include #define maxn 100005class node/*区间结点*/{ public: int l, r; long long sum_, toadd;/*toadd为待加的值*/};int a[maxn] = {0};node no[maxn << 2];long long ans = 0;void build(int le, int ri, int id)/*构建*/{ no[id].l = le; no[id].r = ri; no[id].toadd = 0; if (le == ri)/*区间中只有一个点*/ { no[id].sum_ = a[le]; return; } int mid = (le + ri) >> 1; build (le, mid, id << 1);/*递归建左右树*/ build (mid + 1, ri, (id << 1) + 1); no[id].sum_ = no[id << 1].sum_ + no[(id << 1) + 1].sum_;}void ask(int le, int ri, int id)/*询问区间结点id,在[le, ri]区间的和*/{ if (no[id].l > ri || no[id].r < le)/*区间结点id不在该区间中*/ { return; } if (no[id].l >= le && no[id].r <= ri)/*id被该区间完全覆盖,此时不需要计算待加值,直接加上sum_即可*/ { ans += no[id].sum_; return; } /*id与该区间相交*/ if (no[id].toadd)/*有未加项*/ { /*更新两个子节点*/ int tmp_id = id << 1; no[tmp_id].sum_ += (no[tmp_id].r - no[tmp_id].l + 1) * no[id].toadd; no[tmp_id].toadd += no[id].toadd; ++tmp_id; no[tmp_id].sum_ += (no[tmp_id].r - no[tmp_id].l + 1) * no[id].toadd; no[tmp_id].toadd += no[id].toadd; no[id].toadd = 0; } /*然后再询问子节点*/ int tmp_id = id << 1; ask(le, ri, tmp_id); ask(le, ri, tmp_id + 1); no[id].sum_ = no[tmp_id].sum_ + no[tmp_id + 1].sum_; return;}void update(int le, int ri, int id, long long delta)/*区间[le, ri]加上delta,对id的影响*/{ /*与上面询问类似*/ if (no[id].l > ri || no[id].r < le) return; if (no[id].l >= le && no[id].r <= ri) { no[id].sum_ += (no[id].r - no[id].l + 1) * delta;/*id的sum_需要保证最新,id子节点的sum_之后可以由id的delta算出*/ no[id].toadd += delta; return; } if (no[id].toadd) { int tmp_id = id << 1; no[tmp_id].sum_ += (no[tmp_id].r - no[tmp_id].l + 1) * no[id].toadd; no[tmp_id].toadd += no[id].toadd; ++tmp_id; no[tmp_id].sum_ += (no[tmp_id].r - no[tmp_id].l + 1) * no[id].toadd; no[tmp_id].toadd += no[id].toadd; no[id].toadd = 0; } int tmp_id = id << 1; update(le, ri, tmp_id, delta); update(le, ri, tmp_id + 1, delta); no[id].sum_ = no[tmp_id].sum_ + no[tmp_id + 1].sum_; return;}int main(){ int n = 0, q = 0; scanf("%d%d", &n, &q); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } build(1, n, 1); char cmd; int x = 0, y = 0; long long z = 0; for (int i = 0; i < q; ++i) { scanf("\n%[CQ]%d%d", &cmd, &x, &y); if (cmd == 'C') { scanf("%lld", &z); update(x, y, 1, z); } else if (cmd == 'Q') { ans = 0; ask(x, y, 1); printf("%lld\n", ans); } } return 0;}