题目

题目描述

如题，已知一个数列，你需要进行下面两种操作：
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的结果。

输入输出样例

输入

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

输出

11
8
20

说明

时空限制：1000ms,128M 数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000

分析

翻译过来就是：给你一颗线段树，区间修改或区间查询。 lazy标记法。#include #include #include #include #include #include #include #include #include //日常头文件 using namespace std; //依然头文件 typedef long long ll; //懒得打 const int N=100900; //数据范围 ll ans; //可能很大 ll a[N]; //可能很大 struct node { ll sum; ll addv; }; node v[N*4]; void Add(ll,ll,ll,ll); //操作2第二步 void pushdown(ll,ll,ll); //向下 void pushup(ll); //向上 void buitre(ll,ll,ll); //建树 ll Query(ll,ll,ll,ll,ll); //区间查询 void update(ll,ll,ll,ll,ll,ll); //区间修改 int main() { int n; int m; scanf("%d",&n); scanf("%d",&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); //以上不解释 buitre(1,n,1); //建树 for(int i=1;i<=m;i++) { int opt; scanf("%d",&opt); if(opt==1) { int x; int y; int k; scanf("%d",&x); scanf("%d",&y); scanf("%d",&k); update(x,y,k,1,n,1); } else//我不信还有第三个操作嘎哈哈 { int x; int y; scanf("%d",&x); scanf("%d",&y); ll answ; answ=Query(x,y,1,n,1); printf("%lld ",answ); } //分开写是因为读入的数的个数不一样 //也可以强制性写一起 } //处理操作 return 0; } void Add(ll l,ll r,ll C,ll rt) { v[rt].sum+=(r-l+1)*C; v[rt].addv+=C; } void pushdown(ll l,ll r,ll rt) { ll mid; mid=(l+r)/2; if(v[rt].addv) { ll C; C=v[rt].addv; Add(l,mid,C,rt<<1); Add(mid+1,r,C,rt<<1|1); v[rt].addv=0; } } void pushup(ll rt) { v[rt].sum=v[rt*2].sum+v[rt*2+1].sum; } void buitre(ll l,ll r,ll rt) { if(l==r) { v[rt].sum=a[l]; return; } ll mid; mid=(l+r)/2; buitre(l,mid,2*rt); buitre(mid+1,r,2*rt+1); pushup(rt); } ll Query(ll L,ll R,ll l,ll r,ll rt) { if(L<=l&&r<=R) return v[rt].sum; ll mid; ll ans; mid=(l+r)>>1; ans=0; pushdown(l,r,rt); if(L<=mid) ans+=Query(L,R,l,mid,rt<<1); if(R>mid) ans+=Query(L,R,mid+1,r,rt<<1|1); return ans; } void update(ll L,ll R,ll C,ll l,ll r,ll rt) { if(L<=l&&r<=R) { Add(l,r,C,rt); return; } ll mid; mid=(l+r)>>1; pushdown(l,r,rt); if(L<=mid) update(L,R,C,l,mid,rt<<1); if(R>mid) update(L,R,C,mid+1,r,rt<<1|1); pushup(rt); } //哦，好长 //妈呀终于完事了调了半天我去