A Simple Problem with Integers

Time Limit: 1 Sec Memory Limit: 256 MB

题目连接

http://poj.org/problem?id=3468

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₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , 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

题意

区间加，区间查询和

题解：

线段树，记住懒操作~

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

//**************************************************************************************

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

struct node

{

    int l,r;

    ll sum,add;

    void fun(ll tmp)

    {

        add+=tmp;

        sum+=(r-l+)*tmp;

    }

}a[maxn*];

ll d[maxn];

void relax(int x)

{

    if(a[x].add)

    {

        a[x<<].fun(a[x].add);

        a[x<<|].fun(a[x].add);

        a[x].add=;

    }

}

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

{

    a[x].l=l,a[x].r=r;

    if(l==r)

    {

        a[x].sum=d[l];

    }

    else

    {

        int mid=(l+r)>>;

        build(x<<,l,mid);

        build(x<<|,mid+,r);

        a[x].sum=a[x<<].sum+a[x<<|].sum;

    }

}

void update(int x,int st,int ed,ll c)

{

    int l=a[x].l,r=a[x].r;

    if(st<=l&&r<=ed)

        a[x].fun(c);

    else

    {

        relax(x);

        int mid=(l+r)>>;

        if(st<=mid)update(x<<,st,ed,c);

        if(ed>mid) update(x<<|,st,ed,c);

        a[x].sum=a[x<<].sum+a[x<<|].sum;

    }

}

ll query(int x,int st,int ed)

{

    int l=a[x].l,r=a[x].r;

    if(st<=l&&r<=ed)

        return a[x].sum;

    else

    {

        relax(x);

        int mid=(l+r)>>;

        ll sum1=,sum2=;

        if(st<=mid)

            sum1=query(x<<,st,ed);

        if(ed>mid)

            sum2=query(x<<|,st,ed);

        return sum1+sum2;

    }

}

int main()

{

    int n=read(),m=read();

    for(int i=;i<=n;i++)

        d[i]=read();

    build(,,n);

    char s[];

    int bb,cc,dd;

    for(int i=;i<m;i++)

    {

        scanf("%s",s);

        if(s[]=='Q')

        {

            bb=read(),cc=read();

            printf("%lld\n",query(,bb,cc));

        }

        else

        {

            bb=read(),cc=read(),dd=read();

            update(,bb,cc,dd);

        }

    }

}

巴特西

poj 3468 A Simple Problem with Integers 线段树区间加，区间查询和