题目描述

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

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;
}
分类:

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注