POJ3468：A Simple Problem with Integers（线段树模板）

A Simple Problem with Integers

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 149972		Accepted: 46526

题目链接：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:

题解：

线段树模板题，注意一下lazy标记的下传操作，标记也是long long 型的。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = 1e5+;

int n,m;

ll a[N];

ll ans;

struct Tree{

    int l,r;

    ll f,w;

}tre[(N<<)+];

void build(int o,int l,int r){

    tre[o].l=l;tre[o].r=r;tre[o].f=;

    if(l==r){

        tre[o].w=a[l];

        return ;

    }

    int mid=l+r>>;

    build(o<<,l,mid);

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

    tre[o].w=tre[o<<].w+tre[o<<|].w;

}

void down(int o){

    tre[o<<].f+=tre[o].f;

    tre[o<<|].f+=tre[o].f;

    tre[o<<].w+=tre[o].f*(tre[o<<].r-tre[o<<].l+);

    tre[o<<|].w+=tre[o].f*(tre[o<<|].r-tre[o<<|].l+);

    tre[o].f=;

}

void update(int o,int l,int r,int val){

    int L=tre[o].l,R=tre[o].r;

    if(L>=l && R<=r){

        tre[o].w+=(ll)val*(R-L+);

        tre[o].f+=val;

        return ;

    }

    down(o);

    int mid=L+R>>;

    if(l<=mid) update(o<<,l,r,val);

    if(r>mid) update(o<<|,l,r,val);

    tre[o].w=tre[o<<].w+tre[o<<|].w;

}

void query(int o,int l,int r){

    int L=tre[o].l,R=tre[o].r;

    if(L>=l && R<=r){

        ans+=tre[o].w;

        return ;

    }

    down(o);

    int mid=L+R>>;

    if(l<=mid) query(o<<,l,r);

    if(r>mid) query(o<<|,l,r);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++) scanf("%I64d",&a[i]);

    build(,,n);

    char s[];

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

        scanf("%s",s);

        if(s[]=='Q'){

            int l,r;ans=;

            scanf("%d%d",&l,&r);

            query(,l,r);

            printf("%I64d\n",ans);

        }else{

            int a,b,c;

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

            update(,a,b,c);

        }

    }

    return ;

}

巴特西

POJ3468：A Simple Problem with Integers（线段树模板）

最新文章

热门文章