题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:
输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出样例#1:

11
8
20

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=1000,M<=10000

对于100%的数据:N<=100000,M<=100000

(数据已经过加强^_^,保证在int64/long long数据范围内)

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define maxn 200000
int  q;
ll n,m,x,y,v,a[maxn];
using namespace std;
struct tree
{
    ll l;
    ll r;
    ll sum;
    ll lazy;
}node[maxn*4];
inline void update(ll x)
{
    node[x].sum=node[x<<1].sum+node[(x<<1)|1].sum;
}
inline void build(ll x,ll l,ll r)
{
    node[x].l=l;
    node[x].r=r;
    node[x].lazy=0;
    if(l==r)
     {
     	node[x].sum=a[l];
     	return;
     }
    ll mid=(node[x].l+node[x].r)>>1;
    build(x<<1,l,mid);
    build((x<<1)|1,mid+1,r);
    update(x);
}
inline void pushdown(ll x)
{
    node[x<<1].lazy+=node[x].lazy;
    node[(x<<1)|1].lazy+=node[x].lazy;
    node[x<<1].sum+=node[x].lazy*(node[x<<1].r-node[x].l+1);
    node[(x<<1)|1].sum+=node[x].lazy*(node[(x<<1)|1].r-node[(x<<1)|1].l+1);
    node[x].lazy=0;
}
inline void add(ll x,ll l,ll r,ll k)
{
    if(node[x].l==l&&node[x].r==r)
     {
     	node[x].lazy+=k;
     	node[x].sum+=k*(r-l+1);
     	return;
     }
    if(node[x].lazy) pushdown(x);
    ll mid=(node[x].l+node[x].r)>>1;
    if(r<=mid) add(x<<1,l,r,k);
     else if(l>mid) add((x<<1)|1,l,r,v);
      else add(x<<1,l,mid,v),add((x<<1)|1,mid+1,r,v);
    update(x);
}
inline ll query(ll x,ll l,ll r)
{
    if(node[x].l==l&&node[x].r==r)
     return node[x].sum;
    if(node[x].lazy) pushdown(x);
    ll mid=(node[x].l+node[x].r)>>1;
    if(r<=mid) return query(x<<1,l,r);
     else if(l>mid) return query((x<<1)|1,l,r);
      else return query(x<<1,l,mid)+query((x<<1)|1,mid+1,r);
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int  i=1;i<=n;i++)
     scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
     {
     	scanf("%d%lld%lld",&q,&x,&y);
     	if(q==1)
     	 {
     	 	scanf("%lld",&v);
     	 	add(1,x,y,v);
          }
        else
         printf("%lld\n",query(1,x,y));
     }
    return 0;
}

欢迎来到睿屿青衫丶

avatar
 
微笑晕爱心心碎调皮难过尴尬惊讶惊吓酷泪奔吐彩虹害羞敲打喝彩抠鼻吐星星眼擦汗大笑蛋糕呲牙瞌睡咒骂吃瓜贪财骷髅鬼脸委屈奋斗笑哭摸头小纠结点赞笑崩发呆绿帽狂汗亲嘴么么机智抑郁色鄙视坏笑白眼左哼哼右哼哼捂嘴鼓掌可怜香肠嘴闭嘴墨镜认错思考拒绝鲜花愤怒嘟嘴不忍直视嘘emm流泪yeah睡觉扔鞋石化生病抽烟吐血偷笑衰兔牙害怕震惊捂嘴笑打盹疑问亲亲指开心喜欢阴险郁闷坏笑2搞怪汪好奇汪机智汪冷漠汪搞怪哈摆拍柴柴犬生气柴流泪柴张嘴柴挥爪柴佩服勾引拳头胜利赞踩滑稽
  订阅  
提醒