luogu3372 线段树模板1

luogu3372 线段树模板1

​​ 题目描述

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

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数据范围内）

样例说明：

110000inline char gc(){ static char now[1<<16], *S, *T; if(S==T){T=(S=now)+fread(now, 1, 1<<16, stdin); if(S==T)return EOF;} return *S++;}inline long long read(){ long long x=0;char ch=gc(); while (ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int l,r,left,right;long long lazy,sum;}tree[N<<2];inline void update(int x){ int l=tree[x].left,r=tree[x].right; tree[x].sum=tree[l].sum+tree[r].sum;}int num,n,m,a[N],root;void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r; if (l==r){tree[x].sum=a[l];return;} int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r); update(x);}inline void pushdown(int x){ if (!tree[x].lazy) return; int l=tree[x].left,r=tree[x].right; tree[l].lazy+=tree[x].lazy;tree[r].lazy+=tree[x].lazy; tree[l].sum+=tree[x].lazy*(tree[l].r-tree[l].l+1); tree[r].sum+=tree[x].lazy*(tree[r].r-tree[r].l+1); tree[x].lazy=0;}void insert1(int x,int l,int r,long long z){ if (l<=tree[x].l&&r>=tree[x].r){ tree[x].lazy+=z;tree[x].sum+=z*(tree[x].r-tree[x].l+1);return; } int mid=tree[x].l+tree[x].r>>1;pushdown(x); if (l<=mid) insert1(tree[x].left,l,r,z); if (r>mid) insert1(tree[x].right,l,r,z); update(x);}long long query(int x,int l,int r){ if (l<=tree[x].l&&r>=tree[x].r) return tree[x].sum; int mid=tree[x].l+tree[x].r>>1;pushdown(x);long long tmp=0; if (l<=mid) tmp+=query(tree[x].left,l,r); if (r>mid) tmp+=query(tree[x].right,l,r); return tmp;}int main(){ freopen("3372.in","r",stdin); n=read();m=read(); for (int i=1;i<=n;++i) a[i]=read(); build(root,1,n); for (int i=1;i<=m;++i){ int op=read(); if (op==1){long long z=0; int x=read(),y=read();z=read(); insert1(root,x,y,z); }else{ int x=read(),y=read(); printf("%lld\n",query(root,x,y)); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。