题目大意

给定一个序列a[1],a[2]……a[n]

接下来给出m种操作，每种操作是以下形式的：

l r d

表示把区间[l,r]内的每一个数都加上一个值d

之后有k个操作，每个操作是以下形式的：

x y

表示把第x种操作一直到第y种操作都执行一遍

最终输出在k个操作结束之后的序列

题目大意

就是线段树的成段更新嘛~~~先用线段树统计每种操作的次数，然后再执行m次成段更新，最后查询到底的查询即可~~~树状数组也可搞，似乎写起来还更简单些~~~还有一个更犀利的O(n)的算法，不过我暂时还没弄懂~~~这里是某大神的题解

代码：

在update和query的时候穿参数传错了，把m和n搞混了，提交上去RE了，搞好久才找出错误。。。。o(╯□╰)o

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define  MAXN 111111

#define lson l,m,s<<1

#define rson m+1,r,s<<1|1

#define x first

#define y second

typedef long long LL;

pair<pair<int,int>,LL> op[MAXN];

LL a[MAXN],addv[MAXN<<2],sumv[MAXN<<2];

void PushDown(int s,int opr)

{

    if(opr==1)

    {

        if(addv[s])

        {

            addv[s<<1]+=addv[s];

            addv[s<<1|1]+=addv[s];

            addv[s]=0;

        }

    }

    else

    {

        if(sumv[s])

        {

            sumv[s<<1]+=sumv[s];

            sumv[s<<1|1]+=sumv[s];

            sumv[s]=0;

        }

    }

}

void update(int opr,int ql,int qr,LL d,int l,int r,int s)

{

    if(ql<=l&&r<=qr)

    {

        if(opr==1)addv[s]+=d;

        else

            sumv[s]+=d;

        return;

    }

    PushDown(s,opr);

    int m=(l+r)>>1;

    if(ql<=m) update(opr,ql,qr,d,lson);

    if(qr>m)  update(opr,ql,qr,d,rson);

}

LL query(int opr,int p,int l,int r,int s)

{

    if(l==r)

    {

        if(opr==1)

            return addv[s];

        else

            return sumv[s];

    }

    PushDown(s,opr);

    int m=(l+r)>>1;

    LL ans=0;

    if(p<=m) ans=query(opr,p,lson);

    else

        ans=query(opr,p,rson);

    return ans;

}

int main()

{

    int n,m,k;

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

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

    for(int i=1;i<=m;i++) scanf("%d%d%d",&op[i].x.x,&op[i].x.y,&op[i].y);

    while(k--)

    {

        int xx,yy;

        scanf("%d%d",&xx,&yy);

        update(2,xx,yy,1,1,m,1);

    }

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

        op[i].y*=query(2,i,1,m,1);

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

        update(1,op[i].x.x,op[i].x.y,op[i].y,1,n,1);

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

        printf("%I64d ",a[i]+query(1,i,1,n,1));

    printf("\n");

    return 0;

}

巴特西

Codeforces295A - Greg and Array(线段树的成段更新)

题目大意

题目大意

代码：

最新文章

热门文章