问题 A: 一个简单的整数问题

时间限制: 5 Sec 内存限制: 128 MB
提交: 75 解决: 25
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1690&pid=0

题目描述

你有N个整数，A1，A2，...，AN。你需要处理两种操作。一种操作是在给定间隔中为每个数字添加一些给定数字。另一种是要求给定间隔中的数字总和。

输入

第一行包含两个数字N和Q.1≤N，Q≤100000。
第二行包含N个数字，A1，A2，...，AN的初始值。 -1000000000≤AI≤1000000000。
接下来的Q行中的每一行代表一个操作。
“C a b c”表示将C添加到Aa，Aa + 1，...，Ab中的每一个。 -10000≤c≤10000。
“Q a b”表示查询Aa，Aa + 1，...，Ab的总和。

输出

你需要回到Q个询问，每个询问一行。

样例输入

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

样例输出

思路：1e5的数据量，暴力区间更新查询肯定会TLE，用线段树可以快很多，此题是线段树的模板题。

代码：

#include<bits/stdc++.h>

using namespace std;

#pragma warning(disable:4996)

#define maxn 100005

#define ll long long

ll chushi[maxn], sum[maxn * 4], lazy[maxn * 4];//记得开4倍空间

void pushup(int rt)

{

    sum[rt] = sum[2 * rt] + sum[2 * rt + 1];

}

void pushdown(int rt, int len)

{

    if (lazy[rt])

    {

         lazy[2 * rt] += lazy[rt];

         lazy[2 * rt + 1] += lazy[rt];

         sum[2 * rt] += (len - len / 2)*lazy[rt];

         sum[2 * rt + 1] += (len / 2)*lazy[rt];

         lazy[rt] = 0;

    }

}

void build(int l, int r, int rt)

{

    lazy[rt] = 0;

    if (l == r)//叶节点赋值

    {

         sum[rt] = chushi[l];

         return;

    }

    int mid = (l + r) / 2;//递归建树——左子树，右子树

    build(l, mid, 2 * rt);

    build(mid + 1, r, 2 * rt + 1);

    pushup(rt);//更新父亲节点的值

}

ll qurry(int x, int y, int l, int r, int rt)

{

    //如果这个区间被完全包括在目标区间里面，直接返回这个区间的值

    if (x <= l && y >= r)

    {

         return sum[rt];

    }

    pushdown(rt, r - l + 1);

    int mid = (l + r) / 2;

    ll ans = 0;

    if (x <= mid)ans += qurry(x, y, l, mid, 2 * rt);//如果这个区间的左儿子和目标区间有交集那么搜索左儿子

    if (y > mid)ans += qurry(x, y, mid + 1, r, 2 * rt + 1);//如果这个区间的右儿子和目标区间有交集那么搜索右儿子

    return ans;

}

void update(int x, int y, int l, int r, int rt, int c)

{

    if (x <= l && y >= r)//区间更新，区间值加C，用到lazy数组去标记

    {

         lazy[rt] += c;

         sum[rt] += (r - l + 1)*c;

         return;

    }

    pushdown(rt, r - l + 1);

    int mid = (l + r) / 2;

    if (x <= mid)update(x, y, l, mid, 2 * rt, c);

    if (y > mid)update(x, y, mid + 1, r, 2 * rt + 1, c);

    pushup(rt);

}

int main()

{

    int n, q;

    cin >> n >> q;

    for (int i = 1; i <= n; i++)scanf("%lld", &chushi[i]);

    build(1, n, 1);

    while (q--)

    {

         char ch;

         scanf(" %c ", &ch);

         if (ch == 'Q')

         {

             ll a, b;

             scanf("%lld %lld", &a, &b);

             printf("%lld\n", qurry(a, b, 1, n, 1));



         }

         else

         {

             ll a, b, c;

             scanf("%lld %lld %lld", &a, &b, &c);

             update(a, b, 1, n, 1, c);

         }

    }

}