codevs 1082 线段树练习 3（区间维护）

codevs 1082 线段树练习 3

时间限制: 3 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，

再接下来一个正整数Q，每行表示操作的个数，

如果第一个数是1，后接3个正整数，

表示在区间[a,b]内每个数增加X,如果是2，

表示操作2询问区间[a,b]的和是多少。

pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

1 2 3 2

2 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

数据范围

1<=n<=200000

1<=q<=200000

#include<iostream>

using namespace std;

#include<cstdio>

#define N 200001

long long int sz[N],n,q,a,b,c,x;

struct node{

    long long int l,r,val,delta;

    node *child[];

}*root=NULL;

void input()

{

    scanf("%d",&n);

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

    scanf("%d",&sz[i]);

}

void update(node *cur)

{

    cur->val=cur->child[]->val+cur->child[]->val;

}

void bulid(node *&cur,long long int l,long long int r)

{

    if(l>r) return ;

    cur=new node;

    cur->l=l;cur->r=r;

    cur->delta=;

    if(l==r)

    {

        cur->child[]=cur->child[]=NULL;

        cur->val=sz[l];

        return;

    }

    long long int mid=(l+r)/;

    bulid(cur->child[],l,mid);

    bulid(cur->child[],mid+,r);

    update(cur);

}

void down(node *cur)

{

    if(cur->child[])

    {

        long long int l1=cur->child[]->l,r1=cur->child[]->r;

        cur->child[]->val+=(r1-l1+)*cur->delta;

        cur->child[]->delta+=cur->delta;

    }

    if(cur->child[])

    {

        long long int l1=cur->child[]->l,r1=cur->child[]->r;

        cur->child[]->val+=(r1-l1+)*cur->delta;

        cur->child[]->delta+=cur->delta;

    }

    cur->delta=;

}

void add(node *cur,long long int l,long long int r,long long int x)

{

    if(l<=cur->l&&cur->r<=r)

    {

        cur->val+=(cur->r-cur->l+)*x;

        cur->delta+=x;

        return ;

    }

    if(cur->delta) down(cur);

    long long int mid=(cur->l+cur->r)/;

    if(l<=mid) add(cur->child[],l,r,x);

    if(r>mid) add(cur->child[],l,r,x);

    update(cur);

}

long long int query(node *cur,long long int l,long long int r)

{

    if(l<=cur->l&&cur->r<=r)

    {

        return cur->val;

    }

    if(cur->delta) down(cur);

    long long int ans=,mid=(cur->l+cur->r)/;

    if(l<=mid) ans+=query(cur->child[],l,r);

    if(r>mid) ans+=query(cur->child[],l,r);

    return ans;

}

int main()

{

    input();

    bulid(root,,n);

    scanf("%d",&q);

    while(q--)

    {

        scanf("%d",&x);

        if(x==)

        {

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

            add(root,a,b,c);

        }

        else {

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

            printf("%lld\n",query(root,a,b));

        }

    }

    return ;

}

teacher's

代码自己尝试写了一下

/*数据类型必须用long long才能过*/

#include<cstdio>

#include<iostream>

using namespace std;

long long n,m;

long long sz[];

struct node

{

    long long val,delta,l,r;

    node * ch[];

}*root=NULL;

long long sv(node * cur)

{

    return cur?cur->val:;

}

void update(node * cur)

{

    cur->val=sv(cur->ch[])+sv(cur->ch[]);

}

void build(node * &cur,long long l,long long r)

{

    if(l>r)return;

    cur=new node;

    cur->l=l;cur->r=r;cur->delta=;

    if(l==r)

    {

        cur->val=sz[l];

        cur->ch[]=cur->ch[]=NULL;

    }

    else

    {

        long long mid=(l+r)/;

        build(cur->ch[],l,mid);

        build(cur->ch[],mid+,r);

        update(cur);

    }

}

void down(node * cur)

{

    if(cur->ch[])

    {

        cur->ch[]->delta+=cur->delta;

        cur->ch[]->val+=cur->delta*(cur->ch[]->r-cur->ch[]->l+);

    }

    if(cur->ch[])

    {

        cur->ch[]->delta+=cur->delta;

        cur->ch[]->val+=cur->delta*(cur->ch[]->r-cur->ch[]->l+);

    }

    cur->delta=;

}

void add(node * cur,long long l,long long  r,long long x)

{

    if(l<=cur->l&&cur->r<=r)

    {

        cur->delta+=x;

        cur->val+=x*(cur->r-cur->l+);

    }

    else

    {

        if(cur->delta)down(cur);

        long long mid=(cur->l+cur->r)/;

        if(l<=mid)add(cur->ch[],l,r,x);

        if(r>mid)add(cur->ch[],l,r,x);

        update(cur);/*注意这个不能更少，当前区间val应该加多少，未知，要先加完他的左右孩子，再回来的时候更新它*/

    }

}

long long query(node * cur,long long l,long long r)

{

    if(l<=cur->l&&cur->r<=r)return cur->val;

    else

    {

        down(cur);

        long long  mid=(cur->l+cur->r)/;

        long long ans=;

        if(l<=mid)ans+=query(cur->ch[],l,r);

        if(r>mid)ans+=query(cur->ch[],l,r);

        return ans;

    }

}

int main()

{

    long long i;

    cin>>n;

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

    build(root,,n);

    cin>>m;

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

    {

        long long a,b,c,d;

        scanf("%lld",&a);

        if(a==)

        {

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

            add(root,b,c,d);

        }

        else if(a==)

        {

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

            printf("%lld\n",query(root,b,c));

        }

    }

    return ;

}

mine

巴特西

codevs 1082 线段树练习 3（区间维护）

codevs 1082 线段树练习 3

最新文章

热门文章